2
$\begingroup$

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!

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

2 Answers 2

4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Alok
    May 28, 2020 at 20:19
  • $\begingroup$ @Alok my pleasure. You can prove that by the mathematical induction. Easy here. $\endgroup$
    – OmG
    May 28, 2020 at 20:44
  • $\begingroup$ 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 :) $\endgroup$
    – Alok
    May 29, 2020 at 6:22
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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)? $\endgroup$
    – Alok
    May 29, 2020 at 7:23
  • $\begingroup$ @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). $\endgroup$
    – dxiv
    May 29, 2020 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.