0
$\begingroup$

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?

  • 0
    Is it $f(n) = f(\lfloor n/2\rfloor)+3n$?2012-06-14
  • 0
    No, there is no floor. Just f(n)=f(n/2)+3n2012-06-14
  • 0
    In this case, what about the value for $f(3)$?2012-06-14
  • 0
    @FrankScience: this is asymptotic behavior.2012-06-14
  • 0
    @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.2012-06-14

1 Answers 1

1

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.

  • 0
    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 Θ2012-06-14
  • 0
    You're right, you don't.2012-06-14