The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
109 views

asked in Algorithms by Boss (8.2k points)
retagged by | 109 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 (57.5k points)
selected by


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,138 questions
36,959 answers
92,026 comments
34,803 users