O(n log n) is my best, Any better?

Tags: #<Tag:0x00007f183804bc88>


Using std::sort() it can solve in that time complexity, Any better Ideas??


I think the question is not described correctly. This question is too easy for linear time solution. I think they wanted an logarithmic time solution. :confused:


You can simply traverse through the array to find max and min in O(n) time complexity


Yes you can do it in O(n), but i don’t think they are expecting O(logn) since they are asking to reduce number of comparisions not asymptotic complexity.

Thank you


The array is not sorted, meaning you would have to check every number, you can’t skip any number.
Therefore O(n) is the best you can do.