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.

enter image description here

enter image description here

  • 1
    $\begingroup$ I think a screenshot of the exact phrasing used in this “part (c)” would be useful in answering your question. $\endgroup$
    – Lynn
    Dec 7 '18 at 23:58
  • 1
    $\begingroup$ Instead of screenshot, we encourage you to transcribe them to text. You may use an OCR to speed up the process. Images are not friendly to searching nor editing. $\endgroup$
    – John L.
    Dec 8 '18 at 0:05
  • $\begingroup$ @Apass.Jack, where can I find information on how to typeset mathematical formulas on stackexchange and would you have an OCR recommendation? $\endgroup$ Dec 8 '18 at 9:56
  • $\begingroup$ You can use LaTeX (also called MathJax) to typeset mathematics, rather than doing it manually with italics. We have a brief tutorial. There is a rather complete reference. $\endgroup$
    – John L.
    Dec 8 '18 at 10:54
  • $\begingroup$ You can just search for "OCR online". Pick one from the top hits. $\endgroup$
    – John L.
    Dec 8 '18 at 10:56

Your Answer

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

Browse other questions tagged or ask your own question.