retagged by
320 views

1 Answer

Best answer
4 votes
4 votes

       T(n) = T(n-1) + 2^n

       = T(n-2) + 2^(n-1) + 2^n

       = T(n-3) + 2^(n-2) + 2^(n-1) + 2^n

       ..........

       ..........

       ..........
       = T(n-k) + 2^(n-(k-1)) + 2^(n-(k-2)) + ............................. + 2^n

Take k = n-1

       = T(1) + 2^(2) + 2^3 + 2^4 + ........................ + 2^n

       = 1 + 2^2 + 2^3 + 2^4 + .......................... + 2^n

       = 2^1 + 2^2 + 2^3 + ................................ + 2^n - 1

       = 2^(n+1) - 1

       = O(2^n)

selected by

Related questions

0 votes
0 votes
0 answers
1
rexritz asked Aug 13, 2023
294 views
$T\left ( n \right )= 8T\left ( \frac{n}{2} \right )+\left ( n\cdot logn \right )^{2.99}$Also can $\mathcal{O}(n^{3})$ be an upper bound to above recurrence relation?
0 votes
0 votes
1 answer
3
im.raj asked May 27, 2016
296 views
T(n) = T(n-1) + nT(1) = 1
0 votes
0 votes
1 answer
4
prateekdwv asked Mar 24, 2016
452 views
What is the solution of following recurrence relation.$B(2) = 1$$B(n) = 3B(n/\log_2(n))+\Theta(n)$​