Re:Perl 11
by bloak on Wednesday October 24, 2018 @10:30AM
(#18292697)
It's important to distinguish between graphs of performance as measured on real hardware and theoretical results from computational complexity theory. It might be clearer to say "near-constant time over the region of interest" if you're talking about the former because "O(1)" has a precise meaning and refers only to what happens in the limit. Real programs usually only work for "small" n: they stop working long before the size of the input reaches 2^(2^(2^1000)), for example. But whether the algorithm is O(1) or not depends only on what happens when the input is bigger than that.
Another way of putting it: if you modify your practical program so that it runs on a theoretical machine that handles any size of input then you will probably find that another term appears in the execution time, one with a "log" in it, and that term eventually dominates when n gets big enough.
Yes, I am being a bit pedantic. But "O(1)" is mathematical notation and you have to be pedantic to do maths properly.
Another way of putting it: if you modify your practical program so that it runs on a theoretical machine that handles any size of input then you will probably find that another term appears in the execution time, one with a "log" in it, and that term eventually dominates when n gets big enough.
Yes, I am being a bit pedantic. But "O(1)" is mathematical notation and you have to be pedantic to do maths properly.