> which a sort should never be

There's certainly a most awesome sort algorithm which is exponential...

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).

I'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.

I 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.

Ah, a fully general O(1) algorithm. Amazing.

The very idea of O(n*(n!)^n) is going to give me nightmares.

You'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.

So 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.

Combinatorial? 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.

With 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.

That's probably why it's misused so much.

What does exponential look like then?

2^n (by the virtue of Big-O, m^n is in O(2^n) for any fixed m).

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.

> 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.

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.

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.)

Thanks for the correction.

Sounds like perhaps you confused with the other direction: that the base of log(n) doesn't matter

This isn't quite right. For example, 3^n is not O(2^n) (see, e.g., https://stackoverflow.com/questions/19081673/big-o-notation-...)

This 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)

More like for any fixed m <= 2 :)