Solving the recurrence T(n) = 3T(n / 2) + n

I'm studying for an exam and I don't know how to get the height of the recursion tree generated by this relation:

T(n) = 3T(n/2) + n

I know the tree will look like this and that I have to add all the terms:

           c*n
          / | \
         /  |  \   
    c*n/2 c*n/2 c*n/2 
      .     .     .
      .     .     .

Thank you!!

Solution

When you have a recurrence relation of the form

T(n) = aT(n / b) + f(n)

then the height of the recursion tree depends only on the choice of b (assuming, of course, that a > 0). The reason for this is that each node in the tree represents what happens when you expand out the above recurrence, and the only place in the above recurrence that you can expand something is in the T(n / b) term. If you increase or decrease a, you will increase or decrease the branching factor of the tree (for example, 2T(n / b) means that there will be two nodes generated when you expand a node, and 3T(n / b) means that there will be three nodes generated when you expand a node), but the branching factor of the tree is independent of the number of levels. It just tells you how many levels there will be. Similarly, changing f(n) will only increase or decrease the total amount of work done at each node, which doesn't impact the shape of the recursion tree.

So how specifically does b impact the height of the tree? Well, in this recurrence relation, each time we expand out T, we end up dividing the size of the input by a factor of b. This means that at the top level of the tree, we'll have problems of size n. Below that are problems of size n / b. Below that are problems of size (n / b) / b = n / b². Generally, at level k of the tree, the problem size will be n / b^k. The recursion stops when the problem size drops to 0 or 1, which happens when k = log_b n. In other words, the height of the recursion tree will be O(log_b n).

Now, just knowing the tree height won't tell you the total amount of work done, because we also need to know the branching factor and the work done per level. There are a lot of different ways that these can interact with one another, but fortunately there's a beautiful theorem called the master theorem that lets you read off the solution pretty elegantly by just looking at a, b, and f(n). In your case, the recurrence is

T(n) = 3T(n / 2) + O(n)

Plugging this into the master theorem, we see that the solution to the recurrence is T(n) = O(n^{log₂ 3}). This is approximately O(n^1.58).