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