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.