I want to know if the recurrence equation $T(n) = 9T(\frac{n}{3}) + nlogn$, can or cannot be solved using master theorem.

At first, I naively went for $O(n^2)$ applying case 1 of master theorem. But then someone pointed out that $f(n)=nlogn$ and $n^{\log_3 9}$ do not have polynomial difference and therefore master theorem cannot be used.

Then I found this proof for master theorem. Proof of case 1 is on page 2 of the document right on top of the page. The proof is based on the inequality:

$f(\frac{n}{b^i}) \leq(\frac{n}{b^i})^{\log_a b -\epsilon}$

which allows the right side of the above inequality to replace f(n) and the proof goes on from there.

As I see it, the above inequality holds for $f(n)=nlogn$ so I think master theorem can be applicable here. I want to know if I am right and if not, why?

  • 2
    $\begingroup$ There are three cases. Check the conditions of each. The master theorem applies if and only if one of the cases match. There is no other condition, and no "magic". (I've never encountered this "polynomial difference" thing.) $\endgroup$
    – Raphael
    Commented Jun 28, 2017 at 4:56
  • $\begingroup$ @Raphael, case 2 and case 3 do not apply here. I am only interested to know if case 1 is applicable or not. If it is applicable, then the answer is definitely O(n^2) since we can easily find an epsilon for which nlogn is O(n^(2-epsioln)). This part seems clear to me because nlogn grows slower than O(n^x) for x>1. $\endgroup$
    – jrook
    Commented Jun 28, 2017 at 5:16
  • $\begingroup$ Why wouldn't it be applicable? Can you reference the exact version of the Master theorem you're using? Does your problem persist with this version? $\endgroup$
    – Raphael
    Commented Jun 28, 2017 at 7:48
  • $\begingroup$ @Raphael, that is my question, too. Is f(n)=nlogn a valid function for applying for applying master theorem case 1 for this problem or not? If it was something like -n^2, master theorem would not be applicable. I want to know if nlogn is invalid too or not. $\endgroup$
    – jrook
    Commented Jun 28, 2017 at 16:06
  • $\begingroup$ In other words, Is nlogn an admissible function for master theorem in this case? $\endgroup$
    – jrook
    Commented Jun 28, 2017 at 16:12

2 Answers 2


Citing CLRS 3ed pp. 94-95:

In the first case, not only must $f(n)$ be smaller than $n^{\log_b a}$, it must be polynomially smaller. That is, $f(n)$ must be asymptotically smaller than $n^{\log_b a}$ by a factor of $n^\epsilon$ for some constant $\epsilon > 0$.

Note that the three cases do not cover all the possibilities for $f(n)$. There is a gap between cases 1 and 2 when $f(n)$ is smaller than $n^{\log_b a}$ but not polynomially smaller.

For your case we have: $$\begin{align} f(n) & = n \log n\\ n^{\log_b a} & = n^2\\ \end{align}$$

We can then show: $$\begin{align} f(n) & = n \log n\\ & < n^{2-\epsilon} & ^{*}\text{for } \epsilon < 1\\ & < n^2 & \text{for } \epsilon > 0\\ \end{align}$$

Then you see we can pick a $\epsilon$ value in the range $(0, 1)$ to get a polynomial difference of at least $n^\epsilon$ because: $$ f(n) < n^{2-\epsilon} < n^2$$

So yes, it is admissible, but your caution is noteworthy, because there are cases where the Master Theorem can not be applied in scenarios similar to this. One example would be the following:

$$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n}$$

You see $\frac{n}{\log n}$, while smaller than $n$, is not polynomially smaller, thus we cannot use the Master Theorem.

$^*$: A polylogarithmic function grows more slowly than any positive exponent


You can apply the case one of master theorem

Case 1 : If $f(n) = \theta(n^c)$ where $c < log_ba$ then $T(n) = \theta(nlog_ba)$. According to the recurrence equation $\theta(n^{1+x})=nlogn$ where $1+x=c$ and $c<2$ because of the obvious reason $logn<n$ hence $c<log_ba$. And the result of the equation will be $\theta(n^2)$.


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.