The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

- All categories
- General Aptitude 1.1k
- Engineering Mathematics 4k
- Digital Logic 1.7k
- Programming & DS 3k
- Algorithms 2.6k
- Theory of Computation 3.2k
- Compiler Design 1.2k
- Databases 2.3k
- CO & Architecture 2.1k
- Computer Networks 2.4k
- Non GATE 795
- Others 1.2k
- Admissions 244
- Exam Queries 419
- Tier 1 Placement Questions 16
- Job Queries 39
- Projects 4

29,138 questions

36,959 answers

92,026 comments

34,803 users