0
$\begingroup$

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)

$\endgroup$
  • $\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 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 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 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 at 20:33
  • $\begingroup$ Perhaps the Wikipedia entry on binary search trees contains such diagrams. $\endgroup$ – Yuval Filmus Jan 7 at 20:37

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.