# Recurrences that cannot be solved by the master theorem

I am given this problem as extra credit in my class:

Propose TWO example recurrences that CANNOT be solved by the Master Theorem.

Note that your examples must follow the shape that $T(n) = aT(n/b) +f(n)$, where $n$ are natural numbers, $a\geq 1$, $b > 1$, and $f$ is an increasing function.

In other words, you can not give examples by making $n \leq 0$, $a < 1$, or $b \leq 1$.

Explain why your recurrences cannot be solved by the master theorem.

I can come up with ones that can't be solved but they don't follow the guidelines stated, like $a$ and $b$ being greater than $1$ or $n$ being a natural number.

-
What happens when $f(n)=n/\log n$? Can you apply the master theorem? – Chris Taylor Oct 12 '12 at 6:06

To paraphrase the article for completeness, the following recurrence $$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log(n)}$$ is inadmissible because the difference between $\frac{n}{\log(n)}$ and $n\log_b(a)$ is not polynomial.
Actually, I forgot you need it increasing. The cosine one is actually not increasing. On top of my head, I cannot think of any other examples (except for silly ones like $\frac{n}{(\log(n))^2}$). – EuYu Oct 12 '12 at 6:15