Using Master Theorem when there are more than 1 elements in the f(n)

463 Views Asked by At

I'm trying to figure out how you would apply the Master Theorem to these two cases: $$ \begin{split} T(n) &= 2 T(n/2) + n \log(n) + 3n\\ T(n) &= 2 T(n/2) + n (\log(n))^2 \end{split} $$

I have some sort of idea for the first one, since you could say that $f(n) = n \log(n) + 3n$ and then since $n\log(n)$ grows fastest, the rest of it can be dropped which gives $T(n) = 2 T(n/2) + n\log(n)$ but I've no idea on how to approach the second one at all. I know how to apply the Master Theorem, I'm just not sure how to apply it to these cases since they're not in the usual form.

1

There are 1 best solutions below

9
On BEST ANSWER

HINT

Putting this into the form $T(n) = aT(n/b) + f(n)$, we have $a=b=2$ and $f(n) = n \ln^2(n)$, so $c = \log_b a = \log_2 2 = 1$, and $$ f(n) = n \ln^2(n) = \Theta\left(n^c \ln^{1+1}n\right), $$ This means you are in the second case of the Master Theorem in Wikipedia formulation, for $k=1$. Can you now complete the problem?

UPDATE

The conclusion of the master theorem is that $$ T(n) = \Theta \left(n^c \log^{k+1} n\right), $$ but we already saw that $c=1$ and $k=1$, from the formulation above. Can you plug in?