# Proof

• Apr 4th 2008, 08:27 AM
BACONATOR
Proof
• Apr 4th 2008, 02: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
• Apr 5th 2008, 09:12 PM
roy_zhang
First $\displaystyle \Theta(g)=\Theta(n)$ represents the set of functions $\displaystyle w(n)$ such that there exists positive constants $\displaystyle c_1,\;c_2$ and $\displaystyle n_0$ such that $\displaystyle 0\le c_1 n\le w(n) \le c_2 n,\;\forall n\ge n_0$. So in order to show that $\displaystyle f\in \Theta(n)$, we need to find out positive constants $\displaystyle c_1,\;c_2$ and $\displaystyle n_0$ such that

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

Dividing $\displaystyle n$ from each parts gives us

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

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

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

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

Roy