The solution of the recurrence T(n) = 3T(n/4) + n log n is

1. AΘ(n² log n)
2. BΘ(n log n)
3. CΘ((n log n)²)
4. DΘ(log log n)

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: B. Θ(n log n)

Explanation

n^(log₄3) ≈ n^0.79, which is polynomially smaller than n log n, and the regularity condition holds. Master theorem case 3: Θ(n log n).