Finding Big-Theta

Question

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?

Answer 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.