1
$\begingroup$

I know that sorting the array take O(logn) time. But why finding the minimum of elements take O(n) time, which is more expensive? If I sort the array, I simply output the first element and this would be my minimum.

$\endgroup$
4
$\begingroup$

Sorting the array using comparison-based method takes $\Omega(n \log n)$. So sorting is obviously more expensive than finding minimum in $\mathcal O(n)$.

In fact finding minimum or sorting takes $\Omega(n)$ to at least read the whole array. For finding minimum it is actually $\Theta(n)$.

If it were true that sorting takes $\mathcal O(\log n)$ then you would be right to use sorting instead.

$\endgroup$
0
$\begingroup$

I think there is no possible way a sorting algorithm can be less than O(n). Best performance we generally get is O(nlogn).

Also, In case of finding the minimum in an array It should be O(n) at least, unless you have more data about the numbers in array. Because you need to go through all the numbers in array at least.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.