# Proof

• April 4th 2008, 09:27 AM
BACONATOR
Proof
• April 4th 2008, 03:24 PM
CaptainBlack
Quote:

Originally Posted by BACONATOR

Well you could start by writting out what it is you have to prove for this to be true.

RonL
• April 5th 2008, 10:12 PM
roy_zhang
First $\Theta(g)=\Theta(n)$ represents the set of functions $w(n)$ such that there exists positive constants $c_1,\;c_2$ and $n_0$ such that $0\le c_1 n\le w(n) \le c_2 n,\;\forall n\ge n_0$. So in order to show that $f\in \Theta(n)$, we need to find out positive constants $c_1,\;c_2$ and $n_0$ such that

$c_1 n \le \frac{n^2+4}{n+4}\le c_2 n,\;\;\forall n\ge n_0$

Dividing $n$ from each parts gives us

$c_1 \le \frac{n^2+4}{n^2+4n}\le c_2$

Consider the function $h(n)=\frac{n^2+4}{n^2+4n}$, given that $n\in Z^{+}$, by differentiation we can find the minimum value of function $h(n)$to be $\frac{2\sqrt{5}+10}{6\sqrt{5}+10}\approx 0.618034$, also realize that $\frac{n^2+4}{n^2+4n}\le 1,\;\forall n\in Z^{+}$. Hence we can pick $c_1=\frac{1}{2},\;c_2=1$ and $n_0=1$, we have

$\frac{1}{2}\le \frac{n^2+4}{n^2+4n}\le 1,\;\;\forall n\ge 1$

this shows that $f\in \Theta(n)$.

Roy