Gate CS 2025 (CS1)| Question - 20 | Algorithms

T(n) = 2T(n−1) + n.2ⁿ
       = 2[2T(n−2) + (n−1) 2^n-1]+n.2ⁿ
       = 2²T(n−2) + 2(n−1) 2^n-1]+n 2ⁿ
      = 2² · [2T(n−3) + (n−2)· 2ⁿ⁻²] + 2(n−1)· 2ⁿ⁻¹ + n· 2ⁿ
By observing, we can write
T(n) = 2ᵏ·T(n−k) +$\sum _{i=0}^{k-1}$  2ⁱ·(n−i)·2ⁿ⁻ⁱ
[∵T(0) = 1 So k = n
T(n) = 2ⁿ · T(0)$\sum _{i=0}^{n-1}$ 2ⁱ · (n − i) · 2ⁿ⁻ⁱ
∴T(n) = 2ⁿ + $\sum _{i=0}^{n-1}$ (n − i) · 2ⁿ
= 2ⁿ + 2ⁿ · [$\frac{n(n+1)}{2}$] 
= Θ(n² · 2ⁿ)