Re:The true cost of linked lists
by ynik on Monday June 06, 2022 @05:45PM
(#31646761)
Big-O/Theta/etc. are just tools for analyzing functions. But it also matters which function you are analyzing.
Typically a program is evaluated in terms of something like the "Random-access machine" where every instruction has a constant cost.
There's a bunch of additional assumptions hidden in this machine model!
In the real world, the speed of light and the Bekenstein bound conspire to make constant-time random-access to a memory of unlimited size impossible. In practice, a random memory access takes O(sqrt(N)) time. We like to pretend that there's a constant worst-case access time, but that only works out because our machines have a limited amount of memory -- it's not really appropriate for an asymptotic analysis.
So complexity theory based on the "Random-access machine" is just measuring a theoretical instruction count that doesn't necessarily correspond to the real-world run-time. There's other models that get closer, e.g. the "cache-oblivious model".
Typically a program is evaluated in terms of something like the "Random-access machine" where every instruction has a constant cost. There's a bunch of additional assumptions hidden in this machine model!
In the real world, the speed of light and the Bekenstein bound conspire to make constant-time random-access to a memory of unlimited size impossible. In practice, a random memory access takes O(sqrt(N)) time. We like to pretend that there's a constant worst-case access time, but that only works out because our machines have a limited amount of memory -- it's not really appropriate for an asymptotic analysis.
So complexity theory based on the "Random-access machine" is just measuring a theoretical instruction count that doesn't necessarily correspond to the real-world run-time. There's other models that get closer, e.g. the "cache-oblivious model".