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.

  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 20 '13 at 21:26
  • $\begingroup$ On the example above that, they used the Master Theorem for $\sqrt n + 42$. $\endgroup$ – user2666425 Sep 20 '13 at 21:53

$\tfrac{3}{4}n+1$ is polynomial, as you say.

You seem to have misunderstood the handout. The example you quote is on slide 7 refers to case 3 of the Master Theorem, as presented on slide 3. The rest of slide 7 uses the Master Theorem to solve the recurrence you're asking about.

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.

| cite | improve this answer | |
  • $\begingroup$ So, you are saying that Slide 7 and Slide 8 are not related at all? My confusion stems from: 'Can we say that ...' on Slide 7. Like they are saying, "Can we say this?" And then on Slide 8, "No, we can't say that, because ...". But you're saying that slide 7 is the conclusion of the problem, and the answer to 'Can we say this..' is yes? $\endgroup$ – user2666425 Sep 21 '13 at 0:32
  • $\begingroup$ 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. $\endgroup$ – David Richerby Sep 21 '13 at 0:35
  • $\begingroup$ 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. $\endgroup$ – user2666425 Sep 21 '13 at 0:37
  • $\begingroup$ 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$.) $\endgroup$ – David Richerby Sep 21 '13 at 0:46
  • $\begingroup$ 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$. $\endgroup$ – user2666425 Sep 21 '13 at 0:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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