Complexity Analysis of a Divide-and-Conquer Recurrence

From the given recurrence relation $T(n) = 2T(n/4) + n^2 \log n$, we identify the parameters:

• $a = 2$ (number of subproblems)
• $b = 4$ (subproblem size division factor)
• $f(n) = n^2 \log n$ (non-recursive work) .

Next, we compute the critical exponent which determines the growth rate of the leaves in the recursion tree: $\log_b a = \log_4 2 = 0.5$ This means the number of leaves grows at a rate of $n^{0.5} = \sqrt{n}$ .

We compare the non-recursive term $f(n) = n^2 \log n$ with the leaf growth term $n^{\log_b a} = n^{0.5}$:

• $f(n) = \Omega(n^{0.5 + \epsilon})$ for any $\epsilon \le 1.5$.
• This indicates that the non-recursive work at the root level dominates the overall work, pointing toward Case 3 of the Master Theorem .

For Case 3 to apply, we must satisfy the [regularity condition]{def="A mathematical constraint in Case 3 of the Master Theorem requiring af(n/b) <= cf(n) for some constant c < 1"} for some constant $c < 1$ and all sufficiently large $n$: $a f(n/b) \le c f(n)$ Substituting our parameters: $2 \left( \left(\frac{n}{4}\right)^2 \log\left(\frac{n}{4}\right) \right) \le c n^2 \log n$ $\frac{1}{8} n^2 (\log n - \log 4) \le c n^2 \log n$ Choosing $c = 1/8 = 0.125 < 1$ satisfies this condition for all $n \ge 4$ .

Since Case 3 is verified, the non-recursive work $f(n)$ dominates the recurrence. Thus, the overall time complexity is: $T(n) = \Theta(f(n)) = \Theta(n^2 \log n)$ This matches option (iii) .