@joshuagrochow@ccanonne I agree with the sentiment, and this is indeed what Robert Sedgewick and other highlight with their approach to the analysis of algorithm. Too bad is so hard to apply! PS: every time a theoretician says "in practice", I think to the "Young Mr Burns" meme...
@joshuagrochow it also depends a lot on where the "hidden constant" shows up. "Achieving accuracy O(alpha) in time blah" means a hell of a different thing when the running time has a quadratic dependence on the accuracy than when it has an exponential one...
@ccanonne Indeed! Also depends on how you use the big-Oh. e.g. in practice 𝑂(2ⁿ) can be way better or way worse than 2ᴼ⁽ⁿ⁾ (depending primarily, but not entirely, on the hidden constant in the latter!).
A big-Oh that hides a factor of 2 in elementary operations might not be so important. But a big-Oh that allows you to ignore finitely many cases, which includes all cases up to size 1billion is a big deal.
Add comment