# Solving a recurrence with the Master Theorem

Problem taken from here (page 3): http://cse.unl.edu/~choueiry/S06-235/files/MasterTheorem-Handout.pdf

$T(n) = 3T(\frac{n}{2}) + \frac{3}{4}n + 1$

$f(n) = \frac{3}{4}n + 1$

It says we cannot use the traditional Master Theorem because $f(n)$ is not a polynomial. How is $\frac{3}{4}n + 1$ not a polynomial? It's a polynomial of degree one with a fractional coefficient.

• What they might have meant was that $f(n)$ is not of the form $Cn^k$. But since $f(n) = \Theta(n)$, everything should be fine. – Yuval Filmus Sep 20 '13 at 21:26
• On the example above that, they used the Master Theorem for $\sqrt n + 42$. – user2666425 Sep 20 '13 at 21:53

$\tfrac{3}{4}n+1$ is polynomial, as you say.
Slide 8 says, "Recall that we cannot use the Master Theorem when $f(n)$ [...] is not polynomial." It goes on to give a limited case where the Master Theorem can work with polylogarithmic $f(n)$, with an example on slide 9. This is completely separate from the example you're asking about on slide 7.
• Slide 7 is an example with polynomial $f$. Slide 8 reminds you that the Master Theorem only works for polynomial $f$. There is no contradiction. – David Richerby Sep 21 '13 at 0:35
• I'm not saying there is a contradiction. I'm making sure I understand your point and the slides. My confusion stemmed because slide 7 ends with "Can we say that $T(n) \in \Theta(n^{1.5849})$", which seemed to imply the negative. – user2666425 Sep 21 '13 at 0:37
• That's just a question about $\Theta$ notation. (The answer is no, because $\log_2 3 > 1.5849$, so there is no constant $c$ such that $n^{\log_2 3}\leq cn^{1.5849}$ for all large enough $n$.) – David Richerby Sep 21 '13 at 0:46
• Wait, what? I think we conclude via Master Theorem that it is $\Theta(n^{1.5849})$. They say on slide 7 that $\log_{2}3$ is $1.5849$. – user2666425 Sep 21 '13 at 0:50