recursion tree method of solving recurrences

Question

I was practicing the recursion tree method using this link: http://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/lec20.html .. 1st example was okay but in the second example he calculates the height of the tree as log(base 3/2) n .. Can anyone tell me how he calculated height ? May be a dumb question but i can't understand! :|

Answer 1

Let me try explain it. The recursion formula you have is T(n) = T(n/3) + T(2n/3) + n. It says, you are making a recursion tree that splits into two subtrees of sizes n/3, 2n/3, and costs n at that level.

If you see the height is determined by height of largest subtree (+1). Here the right-subtree, the one with 2n/3 element will drive the height. OK?

If the above sentence is clear to you, lets calculate height. At height 1,we will have n*(2/3) elements, at height 2, we have n*(2/3)^2 elements,... we will keep splitting till we have one element left, thus at height h

 n*(2/3)^h <= 1
 (take log both side)
 log(n) + h*log(2/3) <= 0
 (log is an increasing function)
 h*log(3/2) >= log(n)
 h >= log(n)/log(3/2)
 h >= log3/2 (n)

I would suggest reading Master Method for Recursion from Introduction to Algorithms - CLRS.