# 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. – aaag Mar 13 '17 at 5:43
• What is peak finding? – Yuval Filmus Mar 13 '17 at 6:43

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})$.