6,121 views
4 votes
4 votes
T(n)=2T(n-1)-1  ,  for n>0

           1            ,  otherwise

What is the time complexity

3 Answers

Best answer
8 votes
8 votes

$T(n)=2T(n-1)-1 , for\ n>0$
$\ \ \ \ \ \ \ \ \  \ \ \ \ \  1 \ \ \ \ \ \ \ \ \ ,  otherwise$

$T(0) = 1$

$T(1) = 2T(0) - 1 = 1$

$T(2) = 2T(1) - 1 = 1$

$T(3) = 2T(2) - 1 = 1$

$T(4) = 2T(3) - 1 = 1$

$...$

So,  $T(n) = 1$, for any value of $n$.

i.e. it remains constant.

Time Complexity = O(1)

selected by
0 votes
0 votes
$T(n)=2T(n-1)-1$

       $=2(2T(n-2))-2$

       .................................

       $=2(2(2.....(2T(n-n))))-(n+1)$

        $=2^{n+1}T(0)-(n+1)$

So, time complexity $O(2^{n})$

No related questions found