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.

  • 1
    What happens when $f(n)=n/\log n$? Can you apply the master theorem?2012-10-12
  • 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
    haha I probably shouldve checked good ol wikipedia. thanks. I need two though, is there any other one on there that Im missing?2012-10-12
  • 0
    Would the last one in the list work for you?2012-10-12
  • 0
    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}$).2012-10-12
  • 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.