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?