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.
Best Answer
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.