The solution of the recurrence relation \(T(n)=3 T(n / 4)+n \lg n\) is

We are given the recurrence T(n) = 3 T(n/4) + n log n.

Apply the Master theorem.

• Identify parameters: a = 3, b = 4, so n^{log_b a} = n^{log_4 3} ≈ n^{0.792}.

• Compare f(n) to n^{log_b a}: f(n) = n log n grows polynomially faster than n^{0.792}. For example, choose ε = 0.2: n log n = Ω(n^{0.792+0.2}) since n log n / n^{0.992} = n^{0.008} log n → ∞.

• Check the regularity condition for the third case: a f(n/4) = 3 * ( (n/4) log(n/4) ) = (3/4) n log n + lower-order terms ≤ c n log n for some c < 1 (e.g., c = 0.8) for large n.

• Conclusion: By the third case of the Master theorem, T(n) = Θ(f(n)) = Θ(n log n).

Answer: Θ(n log n).