retagged by
232 views
0 votes
0 votes
What is order of T(n) ?

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

T(n) = 1 , n=1

A) O(2$^{n}$)

B) O(n.2$^{n}$)

C) O(2$^{2n}$)
retagged by

1 Answer

Best answer
0 votes
0 votes
Given is $T(n) = T(n-1) + 2^n$.

After $k$ iterations, the recurrence will look like:

$T(n) = T(n-k) + (2^n + 2^{n-1} + 2^{n-2} + \dots + 2^{n-k+1})$

This recurrence will terminate when $n-k = 1 \implies k = n-1$.

Substituting the same above, we get:

$T(n) =  1 + (2^n + 2^{n-1} + 2^{n-2} + \dots + 2^{2})$ which is a GP with a sum of $\frac{4(2^{n-1} -1)}{2}$ which is $O(2^n)$
selected by
Answer:

Related questions

0 votes
0 votes
1 answer
1
Çșȇ ʛấẗẻ asked Mar 14, 2023
408 views
Solve the following recurrences using recursion tree method and write the asymptotic time complexity T(n)=T(n/2)+n^2
1 votes
1 votes
0 answers
2
srestha asked May 19, 2019
594 views
Let $A(n)$ denotes the number of $n$ bit binary strings which have no pair of consecutive $1’s.$ what will be recurrence relation for it and what will be it’s Time Co...
0 votes
0 votes
0 answers
3
eyeamgj asked Nov 19, 2018
471 views
WHAT IS RECURRENCE RELATION ?I M GETTING T(n-2)+1
0 votes
0 votes
1 answer
4
eyeamgj asked Jun 24, 2018
397 views
consider the following c program A(n){if(n<=1)return(n2 +n+1)elsereturn(5A(n/2)+3A(n/2)+MA(n))}where MA(n) has complexity O(n2).1.what is the recurrence relation for valu...