retagged by
1,650 views
3 votes
3 votes
what is the tightest upper bound of

T(n)=T(n-1)+2n
retagged by

1 Answer

Best answer
7 votes
7 votes
$\begin{align*} &\Rightarrow T(N) - T(N-1) = 2^{N} \\\\ &\Rightarrow \text{Adding summation to the both sides,} \\\\ &\Rightarrow \sum_{N=1}^{N=N}T(N) - T(N-1) = \sum_{N=1}^{N=N} 2^{N}\\ \\ &\Rightarrow T(N) - T(0) = 2^{1} + 2^{2} + 2^{3} + ............ + 2^{N}\\\\ &\Rightarrow T(N) - T(0) = 2^{N+1} -2\\\\ &\Rightarrow T(N) - T(0) = O(2^{N})\\ \end{align*}$
selected by

Related questions

1 votes
1 votes
0 answers
1
syncronizing asked Mar 15, 2019
1,253 views
Is this the correct way to solve ?Q) int algorithm(int n){ int sum =0;k,j; for (k=0;k<n/2;k++) for(j=0;j<10;j++) sum++; return 4*algorithm(n/2)*algorit...
1 votes
1 votes
1 answer
2
VikramRB asked Jan 20, 2019
1,005 views
What is the time complexity of the following recurrence relation and step to derive the same$T(n) = T(\sqrt{n}) + log(logn)$
0 votes
0 votes
2 answers
3