4 votes 4 votes Algorithms algorithms logarithmic-function time-complexity made-easy-test-series + – Arnabi asked Jan 7, 2017 retagged Jul 7, 2022 by Lakshman Bhaiya Arnabi 448 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
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*}$ dd answered Jan 8, 2017 selected Jan 8, 2017 by srestha dd comment Share Follow See all 0 reply Please log in or register to add a comment.
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) Pavan Kumar Munnam answered Nov 27, 2016 Pavan Kumar Munnam comment Share Follow See 1 comment See all 1 1 comment reply shayal chhabra commented Dec 14, 2016 reply Follow Share Can u explain how to solve this type of questions i m not understanding.... 0 votes 0 votes Please log in or register to add a comment.