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