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.

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

Powered by vBulletin® Version 4.2.5 Copyright © 2019 vBulletin Solutions Inc. All rights reserved.