Thread: 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))?

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

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?

Hmm why do most people use ln x/ln y instead of log x/ log y? The produce the same results. Interesting, very interesting

thanks for the link.