Thread: Proof

1. Proof

Any advice?

2. Originally Posted by BACONATOR
Any advice?
Well you could start by writting out what it is you have to prove for this to be true.

RonL

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