3
$\begingroup$

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.

  • 0
    I do not understand what is meaningful about the problem quoted here. It is already quite silly to have to learn the master theorem, when the general techniques are far more useful. For example, the recurrence relation in EuYu's answer is easy to solve: Let $f(n) = T(n)/n$. Then $f(n) = f(n/2) + 1/\log(n)$. Let $g(k) = f(2^k)$. Then $g(k) = g(k-1) + 1/k$. It is now easy to find lower and upper bounds for $g$ using definite integrals, so $g(k) \in ln(k)+O(1)$ and hence $f(n) \in \log\log(n)+O(1)$.2018-09-11

2 Answers 2

3

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.

  • 0
    ok that one will work I guess i can use it, i mean, its not wrong!2012-10-12
1

Take any equation where a is a fraction. Since for master theorem a should be integral multiple, master's theorem can not be applied.