Does there exist a sorting algorithm with average time complexity better than O(n * log(n)) on a list of integers?
30
1kṀ59752100
97%
chance
1H
6H
1D
1W
1M
ALL
The input is a list of integers from 1 to n in a random order. What matters is the average time taken, not best or worst case. It does not have to be stable. Anthropic effects and other cheesy special cases are ignored.
Resolves YES when one is provided. Resolves NO when this is proven impossible.
This question is managed and resolved by Manifold.
Get 
1,000 to start trading!
1,000