# Why is big omega of peak finding Omega(lg n)?

Why is big omega of finding a peak in an unsorted array Omega(lg n), not Omega(1)?

I understand that peak finding is O(lg n), because in the worst case, we find a peak in the last possible step, so when drawing a decision tree, the height of the tree (lg n) would be the worst case situation. However, in the best case, can't we get "lucky" and find a peak in the first try?

• @ gridproquo It depends upon the algorithm. Please write the pseudocode of the peak finding algorithm you are using. – Call_on_Duty Mar 13 '17 at 5:43
• What is peak finding? – Yuval Filmus Mar 13 '17 at 6:43

## 1 Answer

I think you got a bit confused with the definition of Big-Omega ($\Omega$). The $\Omega(f(n))$ is a lower bound for an algorithm. It means that your algorithm's running time can not be less than $kf(n)$ where $k$ is a constant. And it applies to worst case not the best case.

edit If you calculate your algorithm running time as $c\log{n}$, it's asymptotic analysis says that it is $\Omega(\log{n})$.

big omega notation

• Isn't the worst case big O? – gridproquo Mar 13 '17 at 2:33
• These "Big" stuff are the boundaries. Big-O is an upper bound boundary and Big-Omega is a lower bound boundary. – Iraj Hedayati Mar 13 '17 at 2:38
• Ah, so I can think of big omega as the worst of the best cases? – gridproquo Mar 13 '17 at 2:39
• You should always forget about the best case in algorithm analysis. It is always worst case. So, Big-Omega is the best case of worst cases. P.S. sometime in very rare cases, we also consider average case – Iraj Hedayati Mar 13 '17 at 2:43