GATE 2024 CS: Time complexity of recurrence T(n) = 2T(n/2) + n log n using Master Theorem Extended Case?

### Definitive Proof via Extended Master Theorem & Recursion Tree **Yes, the extended Master Theorem directly applies.** When $f(n) = \Theta(n^{\log_b a} \log^k n)$ with $k \ge 0$: $$T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$$ #### Step-by-Step Derivation: 1. $a = 2, b = 2 \implies n^{\log_2 2} = n$. 2. Here $f(n) = n \log n = n^1 \log^1 n$, so $k = 1$. 3. Substituting into the formula: $$T(n) = \Theta(n^1 \log^{1+1} n) = \mathbf{\Theta(n \log^2 n)}$$ #### Verification via Akra-Bazzi: $$p = 1 \implies g(u) = u \log u$$ $$T(x) = \Theta\left(x^p \left( 1 + \int_1^x \frac{g(u)}{u^{p+1}} du \right)\right) = \Theta\left(x \left( 1 + \int_1^x \frac{u \log u}{u^2} du \right)\right)$$ $$\int_1^x \frac{\log u}{u} du = \frac{1}{2} \log^2 x$$ Hence $T(n) = \Theta(n \log^2 n)$. Perfect agreement!