# 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

You might wanna see the wikipedia link to the Master's theorem. They have a list of inadmissible equations, and the second one should suit your purposes.

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.

-
haha I probably shouldve checked good ol wikipedia. thanks. I need two though, is there any other one on there that Im missing? – user1730008 Oct 12 '12 at 6:08
Would the last one in the list work for you? – EuYu Oct 12 '12 at 6:13
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
ok that one will work I guess i can use it, i mean, its not wrong! – user1730008 Oct 12 '12 at 6:20