GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
92 views

asked in Algorithms by Boss (6k points)  
retagged by | 92 views

1 Answer

+2 votes
Best answer

$\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*}$


 

answered by Veteran (50.5k points)  
selected by


Top Users Jul 2017
  1. Bikram

    3960 Points

  2. manu00x

    2464 Points

  3. Debashish Deka

    1848 Points

  4. joshi_nitish

    1654 Points

  5. Arjun

    1290 Points

  6. Hemant Parihar

    1184 Points

  7. Arnab Bhadra

    1100 Points

  8. Shubhanshu

    1052 Points

  9. Ahwan

    900 Points

  10. rahul sharma 5

    702 Points


24,018 questions
30,955 answers
70,327 comments
29,337 users