Interview Question

Question

Given an Unsorted array, Find maximum in less than O(n) time?

How can we do this?

Comments

It's not possible - you'll have to look at every element once so the lower bound for this is $\Omega(n)$.

---

@goxul it should take $\Theta (n)$ and not $\Omega (n)$ to find maximum and minimum as we always have to search through all numbers.

---

$\Theta(n)$ also implies that $\Omega(n)$ holds, @Swapnil Naik

---

Yes, but Θ(n) would be more appropriate for a given condition.

---

Bubble Sort won't be right because it will take at least O(n) time right? Am I doing anything wrong here?

Answer 1

I think a simple looping through the array once is enough

 FindMax( A[] ):
   max=A[0]
   for i in A:
     if(i>max):
       max=i
   return max