Interview Question

Question

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

How can we do this?

Comments

$\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