News for hackers. Stuff that matters.

A comment on O(n^2), again, now in Windows Management Instrumentation. Parent comment

Re:O(n^2), again, now in Windows Management Instrumentation by aliceryhl on Monday December 09, 2019 @04:26PM (#21746774)
This is untrue: There's no constant k such that k*2^n > 3^n for all n. In general O(a^n) is strictly stronger than O(b^n) if a > b.

This is why you sometimes see complexities that are e.g. O(1.3894732894^n) in wikipedia articles on the best known cases for various algorithms.

[ Parent | on HN ]
Re:O(n^2), again, now in Windows Management Instrumentation by thaumasiotes on Monday December 09, 2019 @04:34PM (#21746866)
> In general O(a^n) is strictly stronger than O(b^n) if a > b.

Typo: O(a^n) is a stronger guarantee than O(b^n) if a < b. It means nothing if a > b.

[ Parent | on HN ]
Re:O(n^2), again, now in Windows Management Instrumentation by xmprt on Monday December 09, 2019 @10:05PM (#21749231)
I took strictly stronger to mean a^n + b^n is O(a^n) so the a^n term holds more weight. The comment didn't mention anything about guarantees.
[ Parent | on HN ]
Re:O(n^2), again, now in Windows Management Instrumentation by thaumasiotes on Tuesday December 10, 2019 @05:05AM (#21751160)
Ah, that would make sense.

I actually thought the most likely intended meaning was that an algorithm in O(a^n) must take asymptotically longer than one in O(b^n) as n goes to infinity (if a > b), which isn't true. (For example, when a > b, then every algorithm in O(b^n) is also in O(a^n), but obviously no algorithm can asymptotically require more time than itself.)

[ Parent | on HN ]
Re:O(n^2), again, now in Windows Management Instrumentation by blattimwind on Monday December 09, 2019 @06:35PM (#21747897)
Thanks for the correction.
[ Parent | on HN ]
Re:O(n^2), again, now in Windows Management Instrumentation by np_tedious on Monday December 09, 2019 @06:56PM (#21748099)
Sounds like perhaps you confused with the other direction: that the base of log(n) doesn't matter
[ Parent | on HN ]