10 ms·
Just to be sure I understand, doesn't the conjecture postulate that O(n log n) is the lower bound, so _anything_ beneath n log n would violate it?
by rincebrain 8y ago
Just to be sure I understand, doesn't the conjecture postulate that O(n log n) is the lower bound, so _anything_ beneath n log n would violate it?
- lovecg 8y agoYes (technically the lower bound would be the small-o(n log n)). The conjecture is that it’s possible to do in O(n log n) time, which this paper proves, and that it’s not possible to do any faster (which is still an open problem).