# Can anyone explain why this is an inadmissible recurrence case that cannot be solved by the master theorem?

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?

• "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. – Raphael Oct 29 '14 at 6:46

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

• 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 – Olórin Oct 28 '14 at 18:48
• 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 – Olórin Oct 28 '14 at 18:53
• 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)$. – Yuval Filmus Oct 28 '14 at 18:53
• 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. – Yuval Filmus Oct 28 '14 at 18:55
• So the solution from master's theorem is only good if it provides a tight bound, otherwise the result is inconclusive – Olórin Oct 28 '14 at 18:55