Time complexity analysis for recurrence relation

Question

I was asked to figure out the time complexity analysis for the following recurrence relation T(n) = 4*T(n-1) + c.

Basically, I did a replacement.. T(n-1) = 4 * T(n-2) + c and so on..

T(n) = 4^k T(1) + c(1 + 4 + 4^2..4^(k-1))

I worked it out as O(4^k) Would like to know if this is right or wrong?

Answer 1

O(4^n) seems to be correct as c(1 + 4 + 4^2 + .. + 4^(n-1)) gives c(4^n - 1) / 3 thus reducing it to O(4^n) and the first part is already O(4^n).

Answer 2

Yes, you are correct.

The homogenous version of your recurrence relation is simply T(n) = 5*T(n-1) - 4*T(n-2) (You can get this by expressing c in the formula for T(n) and in the formula for T(n-1) and then equating them).

The characteristic polynomial of the relation is then x^2 - 5x + 4 = 0. Solving this you get the roots 1 and 4. Hence any solution of the recurrence relation has form a * 4^n + b * 1^n, which simplifies to a * 4^n + b. The values of a and b depend on your initial conditions (the value of c and T(0)). For example, for c = 1 and T(1) = 1, the solution is 1/3 * 4^n - 1/3 - you can check this yourself!

The overall strategy of solving these simple types of recurrence relations is described in the Wiki.