For the question below, it is asking to prove the lower bound on the worst case is log(n). I have no problem proving this and the solution makes 100% sense to me. However, there is a comment at the bottom of the solution which asks why we had to assume that if the loop does not return early, then it runs for omega log(n) iterations. Why is it not obvious based on the fact that the upper bound on the worst case is log(n)? I hope someone can help.