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?

  • $\begingroup$ @ gridproquo It depends upon the algorithm. Please write the pseudocode of the peak finding algorithm you are using. $\endgroup$
    – user35837
    Mar 13, 2017 at 5:43
  • $\begingroup$ What is peak finding? $\endgroup$ Mar 13, 2017 at 6:43

1 Answer 1


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

enter image description here

big omega notation

  • $\begingroup$ Isn't the worst case big O? $\endgroup$
    – gridproquo
    Mar 13, 2017 at 2:33
  • $\begingroup$ These "Big" stuff are the boundaries. Big-O is an upper bound boundary and Big-Omega is a lower bound boundary. $\endgroup$ Mar 13, 2017 at 2:38
  • $\begingroup$ Ah, so I can think of big omega as the worst of the best cases? $\endgroup$
    – gridproquo
    Mar 13, 2017 at 2:39
  • 1
    $\begingroup$ 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 $\endgroup$ Mar 13, 2017 at 2:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.