0
$\begingroup$

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?

$\endgroup$
  • 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 Jun 28 '17 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 Jun 28 '17 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 Jun 28 '17 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 Jun 28 '17 at 16:06
  • $\begingroup$ In other words, Is nlogn an admissible function for master theorem in this case? $\endgroup$ – jrook Jun 28 '17 at 16:12
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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