1
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ @ gridproquo It depends upon the algorithm. Please write the pseudocode of the peak finding algorithm you are using. $\endgroup$ – aaag Mar 13 '17 at 5:43
  • $\begingroup$ What is peak finding? $\endgroup$ – Yuval Filmus Mar 13 '17 at 6:43
1
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Isn't the worst case big O? $\endgroup$ – gridproquo Mar 13 '17 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$ – Iraj Hedayati Mar 13 '17 at 2:38
  • $\begingroup$ Ah, so I can think of big omega as the worst of the best cases? $\endgroup$ – gridproquo Mar 13 '17 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$ – Iraj Hedayati Mar 13 '17 at 2:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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