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?
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?
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:
If one of these conditions holds, then you can apply the relevant section of the Master Theorem.