The best case is O(n), and the worst case is that someone checks why.
You must log in or register to comment.
Really annoys me that this is actually O(n log n) because for large enough n the merge sort will take longer than n*1e6 second. Randall should know better!
You should know better too! Behaviour at large n is irrelevant to “best case” complexity analysis of sorting algorithms
Of course it still matters, you just take the best case for n as n→∞, instead of the worst or average case.