8 ms·
n^2 is polynomial, not exponential. If it was truly exponential (which a sort should never be unless you've decided to solve an arbitrary 3-SAT problem while so
by vecter 7y ago
n^2 is polynomial, not exponential. If it was truly exponential (which a sort should never be unless you've decided to solve an arbitrary 3-SAT problem while sorting a list), then it would've blown up in your face much sooner.
- ww520 7y agoYou're correct n^2 is polynomial, not exponential. It was just an exaggerated figure of speech. BTW, O(n) and O(n log n) are also polynomial; it just doesn't have the punch to it.
- paulddraper 7y agoSo the more precise term would be quadratic. "Exponential" is indeed misused. Half the time I hear it, it is lower, like quadratic or cubic. The other half the time is higher, like combinatorial.
- emn13 7y agoCombinatorial? Seriously? The difference between exponential and cominatorial is essentially purely theoretical when it comes to computational complexity. In practice, even the difference between n and n log n is barely relevant, and the exponential and combinatorial are the exponentiation thereof. Nobody ever, ever deals with processes large enough where the difference both matters, and the process completes. Even a tiny scaling factor in the exponent and a moderate base means the point at which a unscaled combinatorial passes it will take more steps that you might as well be waiting for the heat death of the universe. But even without any scaling factors, don't underestimate the size of the numbers involved. If you had two threads, one simply counting up to some n! upper bound, and the other up to 10^n - how long do you think the minimum problem size would take for the "slow" combinatorial to actually be slower than the exponentiation? Hint: at 4GHz and 1 op/cycle... Let's just say I'm not holding my breath that our species will still be around then. And even a tiny scaling factor to the mix... I mean, if you're trying to estimate computational complexity at least, this nuance seems pointless. But quadratic vs. exponential really matters, with plausible parameters.
- paulddraper 7y agoThat's probably why it's misused so much.
- MaximumYComb 7y agoWith n = 26, the combinatorial process takes 4 times as long. 4 x 10^26 "counts". Googles SHA1 collision attack two years ago used roughly 10^19 computations. So we're off by a factor of 10^7. I'm curious if the rise of quantum computers will make the differences between exponential and combinatorial meaningful in a practical sense.
- Craighead 7y agoWhat 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.)
- chx 7y ago> which a sort should never be There's certainly a most awesome sort algorithm which is exponential... https://www.dangermouse.net/esoteric/bogobogosort.html https://www.dangermouse.net/esoteric/bogobogosort.html They are not even sure what the complexity is but it's like O(n!^(n-k)) or O(n*(n!)^n).
- vecter 7y agoI'm aware of bogosort and its crazy variants, but let's not be ridiculous here. You could make any "sorting" algorithm arbitrarily bad if you'd like by doing such silly but useless things.
- samatman 7y agoI propose Boltzmann sort: wait around until the heat death of the universe, and a Boltzmann brain will emerge from the cosmos, and sort your values while contemplating infinity.
- thewakalix 7y agoAh, a fully general O(1) algorithm. Amazing.
- Graham24 7y agoThe very idea of O(n*(n!)^n) is going to give me nightmares.