I need to use the Master Theorem to find $\Theta(f(n))$ if $f(n)=f(n/2)+3n$ and $f(1)=3$

I don't know how to use the MT in this case, can anyone provide help?

  • $\begingroup$ Is it $f(n) = f(\lfloor n/2\rfloor)+3n$? $\endgroup$ – Yai0Phah Jun 14 '12 at 11:12
  • $\begingroup$ No, there is no floor. Just f(n)=f(n/2)+3n $\endgroup$ – Leng Jun 14 '12 at 11:18
  • $\begingroup$ In this case, what about the value for $f(3)$? $\endgroup$ – Yai0Phah Jun 14 '12 at 11:20
  • $\begingroup$ @FrankScience: this is asymptotic behavior. $\endgroup$ – M.B. Jun 14 '12 at 11:24
  • $\begingroup$ @M.B.: Even if it's asymptotic, it doesn't preclude $f(n) = n^{n^n}$ for odd $n$, which would break all your asymptotics. I think, however, that we know what is meant, but the formulation is not exact. $\endgroup$ – jpalecek Jun 14 '12 at 11:37

The Master Theorem concerns relations of the form

$$f(n) = a f(n/b) + g(n)$$

which fits your problem with $a=1$, $b=2$ and $g(n)=3n$.

Begin by computing the quantity $\log_ba = \log_21=0$, and check which (if any) of the following three quantities are satisfied:

  • $g(n)=O(n^{\log_ba-\epsilon})$ for $\epsilon>0$
  • $g(n)=\Theta(n^{\log_ba} \log^k n)$ for $k\geq 0$
  • $g(n)=\Omega(n^{\log_ba+\epsilon})$ for $\epsilon>0$, and $ag(n/b)\leq cg(n)$ for some constant $c$ and $n$ sufficiently large

If one of these conditions holds, then you can apply the relevant section of the Master Theorem.

  • $\begingroup$ Yep, that's it. Just one more thing, why am i given f(1)=3? As i can see i don't need it to find Θ $\endgroup$ – Leng Jun 14 '12 at 12:12
  • $\begingroup$ You're right, you don't. $\endgroup$ – Chris Taylor Jun 14 '12 at 12:13

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.