2 ms·
> 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.
by thaumasiotes 7y ago
> 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.
- xmprt 7y agoI 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.
- thaumasiotes 7y agoAh, 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.)