How do you find the height of the recurrence tree?

Question

I understand that when you have T(n) in the form T(n) = a*T(n/b) + cn that the height h = base b of n and the tree goes towards T(1) (How to determine the height of a recursion tree from a recurrence relation?). But I am confused about how to find the height of T(n) in the form T(n) = aT(n-b) + cn. The subtraction of b is totally throwing me off. Does T(n) still go to T(1)? How do you find the height of the tree?

If this isn't the correct forum, please direct me towards the correct site.

Answer 1

In a recurrence relation, each "level" of the tree corresponds to a recursive function call. In the old scenario, we were dividing. This can be thought of as breaking the problem down into multiple subproblems.

Consider this function, which computes a factorial:

function fact(n) {
    if(n == 0) return 1
    else return n*fact(n-1);
}

This function differs from the above in that it calls itself only once. The recursion tree is linear, because in each recursive call, the problem is broken down into one subgroup.

Returning to the relation T(n)=a*T(n-b)+cn, note that we could add another constant d=1, and write it like this:

T(n)=a*T(n/d-b)+cn

Now this relation shares the form of the original relation, and we can see that it is being broken down into 1 subgroup with each step. As such, this relation corresponds to an algorithm with linear recursion tree (i.e. O(n)).

The -b term is a necessity to cause the problem to shrink in size. If b=0, then T(n) = a*T(n) would clearly be nonterminating. As long as we can be sure that at each step, the size of the input is always decreasing, then we can be sure the function will eventually reach n=1.

Here you can find a image of a recursion tree for the factorial algorithm. You already linked a version for the case with a b-ary tree. http://faculty.cs.niu.edu/~freedman/241/241notes/recur.gif