I think you're confusing the notion of "best case", "average case" and "worst case" with the notion of asymptotic growth rates.


The thing is, if a function is in O(n log n), then the function is...