4 ms·
What does exponential look like then?
by Craighead 7y ago
What does exponential look like then?
- blattimwind 7y ago2^n (by the virtue of Big-O, m^n is in O(2^n) for any fixed m).
- ammen99 7y agoThis is not true, consider taking the limit 3^n/2^n as n goes to infinity, the limit is infinity, hence 3^n is not O(2^n)
- aliceryhl 7y agoThis 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.
- 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.)
- blattimwind 7y agoThanks for the correction.
- np_tedious 7y agoSounds like perhaps you confused with the other direction: that the base of log(n) doesn't matter
- flugaflusen 7y agoThis isn't quite right. For example, 3^n is not O(2^n) (see, e.g., https://stackoverflow.com/questions/19081673/big-o-notation-of-exponential-functions https://stackoverflow.com/questions/19081673/big-o-notation-...)
- layoutIfNeeded 7y agoMore like for any fixed m <= 2 :)