3
$\begingroup$

Wikipedia says that the following recurrence is inadmissible since there is a non-polynomial difference between $f(n) = \frac{n}{\log n}$ and $n^{\log_b a}$:

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

In human language, what does non-polynomial difference mean? Why was $n/\log n$ compared to $n^{\log_ba}$ in the first place?

In addition, what happens if I replaced $n/\log n$ with $n/\log^*n$, where $\log^*n$ is the log-star function. Would a similar type of analysis take place?

$\endgroup$
  • $\begingroup$ "Inadmissable" is a strong choice of word. The Master theorem does not solve all recurrences -- this is one it does not. Prove by checking the conditions of the cases. For perspective, note our reference question. $\endgroup$ – Raphael Oct 29 '14 at 6:46
3
$\begingroup$

A non-polynomial difference just means that the quotient $\frac{n/\log n}{n^{\log_b a}} = \frac{1}{\log n}$ is not a polynomial, where here $a=b=2$. To see why this is a problem, let's try to apply the master theorem.

Case 2 states that if $f(n) = O(n^{\log_b a} \log^k n)$ for some $k \geq 0$ then $T(n) = O(n^{\log_b a} \log^{k+1} n)$. In our case we can choose $k = 0$ and obtain the bound $T(n) = O(n\log n)$. If we also had $f(n) = \Omega(n^{\log_b a} \log^k n)$ then $T(n) = \Omega(n^{\log_b a} \log^{k+1} n)$, but this doesn't hold in our case.

Case 1 states that if $f(n) = O(n^c)$ for $c < \log_b a$ then $T(n) = O(n^{\log_b a})$. In our case $c = 1$ so this case doesn't apply.

Case 3 states that if $f(n) = \Omega(n^c)$ for some $c > \log_b a$ then $T(n) = \Omega(n^c)$. In our case $c < 1$ so this case also doesn't apply.

Summarizing, the master theorem only gives the upper bound $T(n) = O(n\log n)$. We trivially have $T(n) = \Omega(n/\log n)$, but this doesn't match the upper bound.

We can determine the exact asymptotics using the Akra–Bazzi method. In our case $p = 1$ and $g(x) = x/\log x$, so $T(n) = \Theta(n(1+G(n))$ where $$ G(x) = \int_1^x \frac{g(u)}{u^2} \, du = \int_1^x \frac{du}{u\log u} = \log\log x. $$ (Formally, we have to change the lower bound of the integration from $1$ to $e$.) We conclude that $T(n) = \Theta(n\log\log n)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ok, I think I understand this some what. So for the first two cases, master theorem doesn't hold because $n^{log_ba}$ grows faster than $n/logn$. The third case doesn't hold because $n/logn$ needs to be lower bounded by non-decaying polynomial i.e. polynomial with positive power. The master theorem gives us an upperbound, and a trivial lowerbound. What does it mean for lowerbound not matching upperbound, is it so that we don't have a tight bound therefore the solution is invalid? Thanks $\endgroup$ – Olórin Oct 28 '14 at 18:48
  • $\begingroup$ And have you taken a look at the case where logn is replaced by logstarn? I think the Akra-Bazzi method is not going to yield a good solution because logstarn is a pathological function $\endgroup$ – Olórin Oct 28 '14 at 18:53
  • 1
    $\begingroup$ The solution is not invalid, it's just that the results are inconclusive. We don't know the exact rate of growth, only an upper bound $O(n\log n)$ and a non-matching lower bound $\Omega(n/\log n)$. $\endgroup$ – Yuval Filmus Oct 28 '14 at 18:53
  • $\begingroup$ Regarding $\log^* n$, on the contrary, the Akra-Bazzi method will yield the exact asymptotics. You'll just have to sweat a little more to approximate the integral. $\endgroup$ – Yuval Filmus Oct 28 '14 at 18:55
  • $\begingroup$ So the solution from master's theorem is only good if it provides a tight bound, otherwise the result is inconclusive $\endgroup$ – Olórin Oct 28 '14 at 18:55

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.