Cheap and Secure Web Hosting Provider : See Now

[Answers] I do not understand why finding the minimum of elements take O(n) time

, , No Comments
Problem Detail: 

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.

Asked By : peter

Answered By : Evil

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/63591

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback