3 ms·
The assumption that the computer you are modeling has an infinite amount of memory finite number of caches is a useful assumption as it dramatically simplifies
by malisper 10y ago
The assumption that the computer you are modeling has an infinite amount of memory finite number of caches is a useful assumption as it dramatically simplifies the analysis and still allows you to use big-O to somewhat accurately analyze the performance of a real computer.
- mindslight 10y agoYou 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.