Finding Maximum and Minimum in an Array

This is most deceiving problem ever, I have seen a problem whose condition is to develop an algorithm to find the second maximum of an unsorted array with T(n)=n+log(n)-2. First I thought that for finding a maximum i haven’t ever used the O(log(n)) solution,i.e by Divide and Conquer method. But as I have a little knowledge(very little) about cricket, I am sure that there’s no way we can declare a winner without conducting n competitions then it came to light that, solution is still O(n).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s