0
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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)$).

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.