I want to understand Binary Search for 2 element list made of 1,2. I draw a tree as below. Is it correct?

enter image description here

If I want to search for an element 2, it will make 2 comparisons. If I want to search for an element 22, it will also make 2 comparisons. But according to formula Θ(lg n), with n=2, it should make only one comparison in worst case. I'm not able to connect these 2 facts. Please help me. (For any even number of elements, I'm not able to draw tree. Because at some point, left side has one node and right side has 2 nodes)

  • $\begingroup$ The formula $\Theta(\log n)$ defines a class of functions. It has no particular value at any given point. $\endgroup$ – Yuval Filmus Jan 7 '19 at 18:09
  • $\begingroup$ So you mean to say Θ(lg n) is just a classification. The exact number of comparisons will not necessarily match with values of Θ(lg n). $\endgroup$ – gmail user Jan 7 '19 at 19:41
  • $\begingroup$ Not exactly. My point is that $\Theta(\log n)$ doesn’t specify any particular value at any single $n$. It only stands in for a function growing logarithmically. The function could be $\log n$, or $2\log n$, or $\log n + \log \log n$ - the notation $\Theta(\log n)$ doesn’t specify which. $\endgroup$ – Yuval Filmus Jan 7 '19 at 20:19
  • $\begingroup$ Thanks for reply. Diagram of even numbers has really baffled me. Would you please give one example diagram for lets say n=8? $\endgroup$ – gmail user Jan 7 '19 at 20:33
  • $\begingroup$ Perhaps the Wikipedia entry on binary search trees contains such diagrams. $\endgroup$ – Yuval Filmus Jan 7 '19 at 20:37

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.