2 ms·
You missed what I was illustrating by referencing bounded memory - every realized program has a finite (therefore constant-bounded) number of states. The point
by mindslight 10y ago
You missed what I was illustrating by referencing bounded memory - every realized program has a finite (therefore constant-bounded) number of states. The point is that such analysis is not useful, because it "cheats" with an misleading implicit constant for the bound.
Similarly, if one is analyzing the performance of a general algorithm and assumes memory access is constant time, then that constant needs to be understood as the full access time of main memory (assuming that's what problems will always fit in).
One cannot casually make this assumption to get an O(n) complexity result, profile the program with a problem size that actually fits in cache, and then combine the two to extrapolate larger running time. They each have different baked-in assumptions.