# Thread: Binary tree search efficiency

1. ## Binary tree search efficiency

If we're putting these values in a binary tree. 8,7,6,5,4,3,2,1, it will be an ordered tree. It will look like an unbalanced tree with all the node on the left side. The search efficiency will be big-Oh(n), right? Well, suppose we have a balance tree. 4 is the root and it's balance. According to my source, the worst code big-Oh is now O(log(n)). How is that? Isn't it Omega(log(n))? Couldn't the worst case for a binary tree still be O(n)? What if in searching the element in a tree is a leaf node all the way at the left-end? The search efficiency would be O(n) woulnd't it, not O(log(n))? 2. 8,7,6,5,4,3,2,1 should be just as fast as 1,2,3,4,5,6,7,8

Way I was taught to figure out what the max number of searches is to take the ceiling value of ( ln(number of values) / ln(2) ). 3. If it is an unbalanced binary tree, O( ln( n ) / ln( 2 ) ) is best-case. Worst case is O( n ).

If it is balanced, worst case is O( ln( n ) / ln( 2 ) ). 4. Originally posted by XSquared
If it is an unbalanced binary tree, O( ln( n ) / ln( 2 ) ) is best-case. Worst case is O( n ).

If it is balanced, worst case is O( ln( n ) / ln( 2 ) ).
For worst case, where did ln(2) come from? 5. Hmm why do most people use ln x/ln y instead of log x/ log y? The produce the same results. Interesting, very interesting 6. Originally posted by Thantos
Hmm why do most people use ln x/ln y instead of log x/ log y? The produce the same results. Interesting, very interesting
Properties of logarithms. Check out the logarithm change of base rule. It's on line 15 of this page It will answer the last two questions.

The ln(2) comes from a base 2 logarithm.  8. Originally posted by confuted
Properties of logarithms. Check out the logarithm change of base rule. It's on line 15 of this page It will answer the last two questions.

The ln(2) comes from a base 2 logarithm.
Yes, but in time analysis the base of a log is irrelevant really. 9. Originally posted by axon
Yes, but in time analysis the base of a log is irrelevant really.
It changes the value of the log. In this case, it gives you the multiplier (1/ln(2)), so it's kinda important... Popular pages Recent additions 