retagged by
448 views

2 Answers

Best answer
3 votes
3 votes

$\begin{align*} &\Rightarrow S = \sum_{r=0}^{k}\left ( r.2^r \right ) \\ &\Rightarrow S \;\;\;\; = 1.2^1 +2.2^2 +3.2^3 +4.2^4 +......+(k-1).2^{k-1} +k.2^k \rightarrow (1)\\ &\Rightarrow 2.S \;= \qquad \;\;\;1.2^2 +2.2^3 +3.2^4 +4.2^5 +...........+(k-1).2^{k} +k.2^{k+1}\rightarrow (2) \\ \\ &(1)-(2)\rightarrow \\ \\ &\Rightarrow -S = {\color{red}{2^1+2^2+2^3+.......2^k}} - k.2^{k+1} \\ &\Rightarrow S = k.2^{k+1} - {\color{red}{2^1+2^2+2^3+.......2^k}} \\ &\Rightarrow S = k.2^{k+1} - \frac{2^1.\left ( 2^k - 1 \right )}{2-1} \\ &\Rightarrow S = k.2^{k+1} - 2^{k+1}+2 =(k-1).2^{k+1} + 2 \\ &\text{ Substitute } k = {\color{red}{\log n-1}} \\ &\Rightarrow S_2 = \left ( {\color{red}{\log n-2}}\right ).2^{\log n} + 2 \\ &\Rightarrow S_2 = \large\color{blue}{\Theta(n.\log n)} \\ \end{align*}$


selected by
0 votes
0 votes
If I take r=logk then it reduces to logk*k over the summation till n and the last term will be n*logn this will be the highest term rest all add constants to it so it will theta(nlogn)
Answer:

Related questions

1 votes
1 votes
1 answer
2
Hira Thakur asked Aug 14, 2016
958 views
Big oh estimate forf(x)=(x+1)log($x^2 +1$)+3$x^2$ is given as1.O(xlogx)2.O($x^2$)3.O($x^3$)4O($x^2$logx)
1 votes
1 votes
1 answer
4
garg div asked Jan 8, 2018
299 views
Consider the following functions:$f1=n^{\log n}$$f2=2^n$$f3=2^{\sqrt{n}}$Which of the following is true with regard to asymptotic growth?A. $f1\leq f3\leq f2$B. $f3\leq f...