0
$\begingroup$

I am given an example of a case where the master theorem does not apply, but it seems like it should apply.

This was the reasoning:

$T(n) = 3T(n/3) + n \log n$ with $ a = 3, b=3, f(n) = n\log n$ and $n\log_b a = n\log_3 3 = n$

$f(n)$ is asymptotically larger than $n\log_b (a)$ , but not polynomially larger. The ratio $n \log n / n = \log n$ is asymptotically less than $n^\epsilon$ for any positive $\epsilon$. Thus, the Master Theorem doesn’t apply here

However, it seems like case 2 of the master theorem should apply here. We have $f(n) = n\log n$, and thus $f(n) = \theta(n^{\log_3 3} \log n$)

Then: $T(n) = \theta(n^{\log_a b} \log^{k+1}n) = \theta(n\log^2 n)$

Which is correct?

$\endgroup$
3
  • $\begingroup$ There is a similar question with the same idea: stackoverflow.com/questions/42511669/… This might also help: stackoverflow.com/questions/15735576/… $\endgroup$
    – klaus
    Oct 26 '17 at 16:29
  • $\begingroup$ How it is case 2 of master theorem? $\endgroup$
    – Mr. Sigma.
    Oct 27 '17 at 0:44
  • 2
    $\begingroup$ It really depends on which "version" of the Master Theorem you use. For the most basic version (as in CLRS Theorem 4.1) then no, case 2 does not apply. This is because case 2 in CLRS requires $f(n) = \Theta(n^{\log_b a}) = \Theta(n)$. For your problem $f(n) = n \log n \not\in \Theta(n)$. However, in any further extension, this definitely falls under case 2. See wikipedia's version for example. $\endgroup$
    – ryan
    Jan 3 '20 at 20:18
3
$\begingroup$

Let's take the slightly more general case where $a=b$ and $f(n)=n\;log\;n$ (in your case, $a=b=3$). Assume the usual restrictions on $a$ and $b$ hold. Then $n^{log_ba}=n$. This might lead us to consider case 3 of the Master Theorem since $f(n)=\Omega(n)$.

However, the theorem requires that there exist an $\epsilon > 0$ such that $n\;log\;n = \Omega(n^{1+\epsilon})$. Is this condition met? Equivalently, is it true that $log\;n = \Omega(n^{\epsilon})$ ? As long as $\epsilon$ is positive, this is never true. The polynomial will grow faster. Therefore, the Master Theorem does not apply. You could use iteration or some other method to solve the recurrence.

After searching around, I've found a few references to a corollary of the Master Theorem that addresses polylogarithmic functions. In this version, if we can show that $f(n)=\Theta(n^{log_ba}log^{k}n)$ for some $k \geq 0$, then we can conclude that $T(n) = \Theta(n^{log_ba}log^{k+1}n)$. In our case, $f(n) = \Theta(n\;log\;n)$ with $k=1.$ Therefore, we could conclude that $T(n)=\Theta(n\;log^{2}n)$. However, I don't think this is commonly referred to (or taught) as part of the Master Theorem.

Reference 1

Reference 2

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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