Binary tree search efficiency

Printable View

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

thanks for the link.
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...