# Binary tree search efficiency

• 10-23-2003
ExCoder01
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))?
• 10-23-2003
Thantos
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) ).
• 10-23-2003
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 ) ).
• 10-23-2003
ExCoder01
Quote:

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?
• 10-23-2003
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
• 10-23-2003
confuted
Quote:

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.
• 10-23-2003
Thantos
• 10-23-2003
axon
Quote:

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.
• 10-23-2003
confuted
Quote:

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...