CODEWITHSUNDEEP
c++calgorithmsortingdata-structures
user3729645
user3729645

Reputation: 147

Find minimum element in an array of unsorted integers faster than O (n)?

Is this possible to find the smallest element of an array of unsorted integers by faster than O (n) time complexity. Space complexity is not a concern.

Upvotes: 1

Views: 1681

Answers (1)

Daniel Kleinstein
Daniel Kleinstein

Reputation: 5502

No, this is not possible. Given an arbitrary array of elements, you must look at each element at least once to definitively state that you have found the minimum element. This means that the necessary time complexity is Ω(n) (see here for more information on Big Omega notation), meaning* that any algorithm that finds the minimum element will take at least c * n operations, where c is constant (in this case, c >= 1).

In other words, if an algorithm took less than n operations, then there must be at least one element in the array that the algorithm did not pass over. Since we have no information about this element (the array is arbitrary), we cannot say that this element is not smaller than the element the algorithm declared to be minimum. So the algorithm is incorrect.

* Note that this is not the formal meaning of Big-Omega notation, but it gets the point across. You can read about the formal definition here.

Upvotes: 22

Related Questions