3 ms·
So, the minimum running time for this would be O(1), but can one estimate the maximum? I don't see how, but maybe I'm missing something.
by martin_a 8y ago
So, the minimum running time for this would be O(1), but can one estimate the maximum? I don't see how, but maybe I'm missing something.
- astrobe_ 8y agoThis is known as BoZosort [1], which is said to be O(n!) on average. [1] https://en.wikipedia.org/wiki/Bogosort https://en.wikipedia.org/wiki/Bogosort
- kevinwang 8y agoI think it may be another factor of n slower than that Edit: wow nevermind, I just read the paper linked to bozo sort in wikipedia. They conjecture that it's O(n!) whereas bogosort is Omega(n*n!). Wow, that's surprising!