PDA

View Full Version : Binary tree search efficiency



ExCoder01
10-23-2003, 06:53 PM
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))?

Thantos
10-23-2003, 07:19 PM
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) ).

XSquared
10-23-2003, 07:24 PM
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 ) ).

ExCoder01
10-23-2003, 07:38 PM
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?

Thantos
10-23-2003, 07:40 PM
Hmm why do most people use ln x/ln y instead of log x/ log y? The produce the same results. Interesting, very interesting

confuted
10-23-2003, 07:45 PM
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 (http://mathworld.wolfram.com/Logarithm.html) It will answer the last two questions.

The ln(2) comes from a base 2 logarithm.

Thantos
10-23-2003, 08:16 PM
thanks for the link.

axon
10-23-2003, 08:20 PM
Originally posted by confuted
Properties of logarithms. Check out the logarithm change of base rule. It's on line 15 of this page (http://mathworld.wolfram.com/Logarithm.html) 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.

confuted
10-23-2003, 10:11 PM
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...