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

Question

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.

• Complexity of Recursion T(n) Function

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 2^n-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!

Answer 1

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).

Answer 2

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.