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

programming
Tags: #<Tag:0x00007f183804bc88>

#1

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


#2

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:


#3

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


#4

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


#5

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.