How to determine the height of a recursion tree from a recurrence relation?

Question

How does one go about determining the height of a recursion tree, built when dealing with recurrence run-times? How does it differ from determining the height of a regular tree?

alt text http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/ch4-9.gif

edit: sorry, i meant to add how to get the height of the recursion tree from the recurrence relation.

Answer 1

What, it's not clearly obvious to you? ;) This is a great question if for no other reason than people like to wave their hands at it. It does become clear with practice, however.

Here's an explanation based on an example from the Introduction to Algorithms by Cormen, et al., Section 4.4.

Consider T(n) = 3T(n/4) + cn^2. The relation tells the time complexity of a problem (e.g. an array) of size n. It's important to remember what n represents. Since the complexity T is defined in terms of T, it's a recurrence relation.

If the height isn't apparent, we can follow the advice of Polya and try to use direct reasoning, draw a picture, or solve some related problem. We can use direct reasoning by simply plugging the right-hand expression for T in wherever T appears,

T(n) = 3T(n/4) + cn^2
     = 3[3T( (n/4)/4 ) + c(n/4)^2] + cn^2
     = 9T(n/16) + c(n/4)^2 + cn^2
     = 9[3T( (n/16)/4 ) + c(n/16)^2] + c(n/4)^2 + cn^2
     = 27T(n/64) + c(n/16)^2 + c(n/4)^2 + cn^2
     ...

Drawing a picture produces a tree. Each recursion produces three branches for each child:

Initial pass
                   ____cn^2____
                  /      |     \
                 /       |      \
            T(n/4)    T(n/4)    T(n/4)


First recursion                 
                   ____cn^2____
                  /      |     \
                 /       |      \
          cn(n/4)^2  cn(n/4)^2  cn(n/4)^2
          /   |   \  /   |   \  /   |   \
       T(n/16)          ...            T(n/16)
                         .
...on down             
                   ____cn^2____
                  /      |     \
                 /       |      \
          cn(n/4)^2  cn(n/4)^2  cn(n/4)^2
          /   |   \  /   |   \  /   |   \
       T(n/16)          ...            T(n/16)
                         .
                         .
                         .
    T(1) ...                            ...  T(1)

On down to what?

Remember that n is the size of the original problem (e.g. the number of elements in an array)¹. This bounds the number of recursions that can happen. The boundary conditions will depend on the situation in which the recursion came about. For an array, you can imagine the recursion continuing until only a single element remains. This would happen at T(1).

How might the boundary be related to the height?

To me, the grand revelation is realizing that the height of the tree is the same as the level at which the boundary is met. This is that "related problem" Polya talks about. We can reformulate the question to be,

At what level does the tree reach the boundary condition?

Looking at the relation or the tree, notice how n/4 is repeatedly plugged into successive recursions. This means the subproblem size (where n is the original problem size) is n/4^i at the ith level. At the boundary, the subproblem size is 1:

                n/4^i = 1
         log_4(n/4^i) = log_4(1)
log_4(n) - log_4(4^i) = 0
             log_4(n) = log_4(4^i)
             log_4(n) = i

The last equation tells us that the tree reaches the boundary condition when i = log_4(n). Since the height of the tree is the level where the boundary condition is met, the tree has height log_4(n).

From here, it's only a matter of generalizing to reach the conclusion @ejel gives that

If T(n) = aT(n/b) + f(n) then the depth of the tree is log base b of n.

As @xpda points out, the height of recursion tree will depend on the algorithm. One take-away which likely generalizes is to consider how the algorithm behaves at its boundaries.

---

¹ The word "problem" may be used in different ways. Foremost, it may mean "the task at hand", such as finding the height of the recursion tree. However, since the tree arises through recursion, the problem reappears in similar form (i.e. subtrees) so that "problem" comes to mean "the size of the set being operated on", such as the number of elements in an array.

Answer 2

The depth of any tree is the smallest number of edges from the node to the tree root node.The depth of root node is 0.

Consider the recursion T(n)=aT(n/b) It results in the following recursion tree

It is clear that depth of tree is $\log_b n$ Depth is same as height of a tree.

Answer 3

If recurrence is in the form of T(n) = aT(n/b) + f(n) then the depth of the tree is log base b of n.

For example, 2T(n/2) + n recurrence would have tree of depth lg(n) (log base 2 of n).

Answer 4

Firstly, if this is a homework question, please mark it as such. The images you link to imply that you're in CS 455, with Professor Wisman. :)

The main hint I'll give is this: The height of the tree is obviously determined by when you get to the "leaves". The leaves of a tree modelling the recurrence relation of a function are the base case. Thus, I would look towards seeing how "quickly" N can shrink to the base case.

Answer 5

The height of the recursion tree depends on the recursive algorithm in question. Not all divide and conquer algorithms have uniformed height trees, just as not all tree structures have uniform heights. If you cannot determine the maximum possible height of the algorithm, or if you need to calculate the actual height of the tree at run time, you can use a variable global to the recursive function, increment it upon the entry to the function, and decrement it upon the function exit. This variable will indicate the current level of the recursive procedure. If necessary, you can maintain the maximum value of this variable in a second variable.