Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
What happens when $f(n)=n/\log n$? Can you apply the master theorem? – Chris Taylor Oct 12 '12 at 6:06
up vote 2 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.