# Finding Big-Theta

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?

• Is it $f(n) = f(\lfloor n/2\rfloor)+3n$? – Yai0Phah Jun 14 '12 at 11:12
• No, there is no floor. Just f(n)=f(n/2)+3n – Leng Jun 14 '12 at 11:18
• In this case, what about the value for $f(3)$? – Yai0Phah Jun 14 '12 at 11:20
• @FrankScience: this is asymptotic behavior. – M.B. Jun 14 '12 at 11:24
• @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. – jpalecek Jun 14 '12 at 11:37

## 1 Answer

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.

• 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 Θ – Leng Jun 14 '12 at 12:12
• You're right, you don't. – Chris Taylor Jun 14 '12 at 12:13