1
$\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$
  • $\begingroup$ Increasing n by 1 doubles the runtime, so intuitively, you should expect exponential runtime, just as your calculation shows. $\endgroup$ – rainer May 28 at 20:01
3
$\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).

| cite | improve this answer | |
$\endgroup$
  • $\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 at 20:19
  • $\begingroup$ @Alok my pleasure. You can prove that by the mathematical induction. Easy here. $\endgroup$ – OmG May 28 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 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.

| cite | improve this answer | |
$\endgroup$
  • $\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 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 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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