On Fri, Feb 23, 2018 at 11:31 AM, Steven D'Aprano <steve+comp.lang.pyt...@pearwood.info> wrote: > Big O analysis is never a substitute for actual timing measurements, and > the assumption behind Big O analysis, namely that only some operations > take time, and always constant time, is never correct. It is only an > approximation to the truth, and as you can see, something which is > algorithmically Big O logarithmic can turn out to scale worse than > linearly once you actually measure the times.
I prefer to describe that as "hidden costs". Any step that has its own non-constant cost becomes a hidden cost. That doesn't mean Big O is itself limited, but that when you analyze a function, you have to think about more than just what's right in front of you. For example: def count_at_max(items): count = 0 for item in items: if item == max(items): count += 1 return count def count_at_max(items): count = 0 peak = max(items) for item in items: if item == peak: count += 1 return count So similar, but one of them runs in O(n²) and the other in O(n). The max() call is a "hidden cost". (Obviously they'll usually be subtler than that, but this is a sledgehammer for demonstrative purposes.) Big O *can* handle this, you just have to take notice of things. ChrisA -- https://mail.python.org/mailman/listinfo/python-list