Recurrance relation: T (n/16) + n log n

Question

Can the master theorem be applied?

Or say for T (n) = 2T (n/16) + n log n, how is the master theorem applied here?

I get a = 2, b = 16 and I am not sure about c and k.

Answer 1

Even if the log (n) term was not there the reduction in work per sub-problem at each level dominates (b > a). Hence in my opinion the complexity shall be dictated by the work done at highest level viz O (nlogn).

Answer 2

To solve such a recurrence relation T(n) = a⋅T(n/b) + f(n), you have to calculate e = logb(a).

Then (for an ε > 0):

1. f(n) ∈ O(ne - ε) ⇒ T(n) ∈ Θ(ne)
2. f(n) ∈ Θ(ne) ⇒ T(n) ∈ Θ(ne⋅log(n))
3. f(n) ∈ Ω(ne + ε) ⇒ T(n) ∈ Θ(f(n))

For more details see Masters Theorem.

So in your case: a = 2, b = 16 ⇒ e = log16(2) = 0.25 holds for case 3,
so T(n) is in Θ(n log n).