# Can this reccurrence recurrence be solved using Master Theorem?

Assume we have: $$T(n)=7T(\frac{n}{2})+n^2\lg{n}$$ Can we solve it using master theorem?

As we know $$n^{\lg_2{7}}\approx n^{2.81}$$. On the other hand, we have $$f(n)=n^2\lg n$$. So we should compare $$n^.081$$ and $$\lg{n}$$. As I know, $$\lg{n}=\mathcal{O}(n^{0.81})$$. So the answer should be $$T(n)=\Theta(n^{\lg7})$$. Am I right? Can we use Master Theorem here? the logarithm make me unsure about it.

## 1 Answer

Yes, that recurrence can be solved using the master theorem, and you got the correct answer but your justification is missing on a detail.

In particular it is false (in general) that a recurrence of the form $$T(n) = aT(n/b) +f(n)$$ has solution $$T(n) \in \Theta(n^{\log_b a})$$ when $$f(n) \in O(n^{\log_b a})$$. As a concrete example, $$T(n) = 4T(n/2) + n^2$$ satisfies $$f(n) = n^2 \in O(n^{\log_2 4})$$ but it has solution $$T(n) \in \Theta(n^2 \log n)$$ (and not $$T(n) \in \Theta(n^2)$$). A trickier example is $$T(n)=2T(n/2) + \frac{n}{\log \log n}$$, where $$\frac{n}{\log \log n} \in o(n) \subset O(n)$$, but the master theorem does not apply.

What you actually need is $$f(n) \in O(n^{\log_b a - \varepsilon})$$ for some constant $$\varepsilon>0$$. This is clearly the case in your recurrence since $$\log n \in O(n^c)$$ for all constants $$c>0$$ (so you can choose any $$\varepsilon$$ in the non-empty open interval $$(0, \log_2 7 - 2)$$).

• So the answer is $T(n)=\Theta(n^{\lg_2{7}})$? Nov 14, 2023 at 13:56
• Yes.$\phantom{}$ Nov 14, 2023 at 13:57