# Complexity of recursion T(n) = 2T(n-1) + C?

I am trying to calculate the Time Complexity of the Recursive Function, suppose this,

function T(int n){
if(n == 1) return 1;
return T(n-1) + T(n-1);
}


the time complexity equation is: T(n) = 2T(n-1) + C, taking C = 1 and T(1) = 1. Now, since I am working on this, I am confused whether I am doing the right process using Back Substitution. This is how I approached the calculation. I have followed the below question, but did not find it very satisfactory, so raising the question again.

This is how I approached the problem:

1. T(n) = 2T(n-1) + 1
2. T(n-1) = 2T(n-2) + 1 //since we have T(n-1) in Eq(1)
3. T(n-2) = 2T(n-3) + 1 //since we have T(n-2) in Eq(2)


Back Substitution to Solve for final complexity

1. T(n-1) = 2(2T(n-3) + 1) + 1
2. T(n) = 2(2(2T(n-3) + 1) + 1) + 1
= 2(4T(n-3) + 1 + 2) + 1
= 8T(n-3) + 1 + 6
= 8T(n-3) + 7
= 8T(n-3) // Ignoring 7, since it is a constant
= 2^3T(n-3)
= 2^kT(n-k)


Substituting the value of K, since base case is n = 1

1. n-k = 1
2. k = n-1

//Substituting the value of k in the above T(n) Equation
T(n) = 2^{n-1}T(n-n+1)
= 2^{n-1}T(1)
= 2^{n-1} * 1
= 2^{n-1}


So from above I got 2n-1, is the above process correct, or needs improvement. I am starting off with time complexity, and this recursion is kind of tricky for me. Please help!

• Increasing n by 1 doubles the runtime, so intuitively, you should expect exponential runtime, just as your calculation shows. – rainer May 28 at 20:01

The exact equation is (if $$T(1) = 1$$):

$$T(n) = 2T(n-1) + 1 = 2(2T(n-2) + 1) + 1 =$$ $$2^2 T(n-2) + 2 + 1 =$$ $$2^2(2T(n-3) + 1) + 2 +‌ 1 = 2^3 T(n-3) + 2^2 + 2 + 1$$

Hence, $$T(n) = 2^{n-1} + 2^{n-2} + \cdots + 1 = 2^n - 1$$ (by mathematical induction).

• I really appreciate that, how easily you broke it into a simpler series, having the equation 8T(n-3) + 7 differs the solution, however, the end equation was same only, that is, 8T(n-3) + 7 = 2^3T(n-3) + 2^2 + 2^1 + 1. Thanks @OmG, I need to learn this thing of identifying the pattern. Just a quick question, what is the problem of solving the same with my approach, could you please throw some light on it? – Alok May 28 at 20:19
• @Alok my pleasure. You can prove that by the mathematical induction. Easy here. – OmG May 28 at 20:44
• Hey @OmG, I am not very good at mathematical induction, could you please share a link so that I can read more about it. Pardon me for my mathematics, but I am willing to learn about since, This is something important which I need to know now. Thanks :) – Alok May 29 at 6:22

For a shortcut to the exact expression, add C on both sides of the recurrence and write it as:

    T(n) + C = 2 (T(n-1) + C)


Define U(n) = T(n) + C then the above gives U(n) = 2 U(n-1).

Therefore U(n) is a geometric progression with common ratio 2, so U(n) = 2^n U(0), then:

    T(n) = U(n) - C
= 2^n U(0) - C
= 2^n (T(0) + C) - C


For C = 1 and T(0) = 0 this reduces to T(n) = 2^n - 1.

• Hey @dxiv, could you please explain how did this equation become 2^n U(0), according to the Geometric Progression. As far as my knowledge is concerned, GP = ar^{n-1}, where r is the common ratio. Taking 2 as your common ratio, then how did you proceed to get 2^n U(0)? – Alok May 29 at 7:23
• @Alok It's the same thing. Using your formula U(n) = U(1) 2^(n-1). But if you consider the progression to start at n=0 then U(1) = 2 U(0) so U(n) = 2 U(0) 2^(n-1) = 2^n U(0). – dxiv May 29 at 7:27