MT for T(n) = 2T(n/2) + n^2 log n

Question

How do we use MT to solve T(n) = 2T(n/2) + n^2 log n?

c = 2 > log_b(a) here, but f(n) = Theta (n^2 log n) instead of purely Theta(n^2).

Besides, for T(n) = 2T(n/2) + n logn, f(n) / n^log_b(a) = log n, there is a non-polynomial difference right? Then why can we use MT for it?

Answer 1

The provided recurrence is of the form T (n) = a T(n/b) + theta (n^k log^pn) where a>=1, b >1, k >=0, p is a real number. The value of a=2, b=2, and k=2, and this means that a < b^k

Since the value of p  >= 0, then T (n) = Theta (n^k log ^p n)

After applying the master theorem, the time complexity for the provided recurrence would be:

T(n) = Theta (n^2 log n) 

Comments

Thank you Amal. Could you please tell me which case of MT are we referring to?

---

Hello, it is case 3.

---

Hi, are you suggesting T(n) = Ө(f(n)) if f(n) = Ω(n^c) where c > log_b(a)? This might be a little different from case 3 on the textbook.

---

Yes, the case 3 in the book states: "If f(n) is too large, then f(n) term dominates".

Answer 2

The answer is: T(n) = Θ(n²log n).

a = 2, b = 2, log_ba = 1, f(n) = n²log n.

f(n) = n²log n = Ω(n^c), if c = 2, yes, c > log_ba = 1, so it is case 3. Then T(n) = Θ(f(n)) = Θ(n²log n).

If f(n) is too large, then f(n) term dominates.

Sometime we can just asymptotically compare f(n) with n^log_ba to find out which term dominates.