Any advice?

Printable View

- Apr 4th 2008, 08:27 AMBACONATORProof
Any advice?

- Apr 4th 2008, 02:24 PMCaptainBlack
- Apr 5th 2008, 09:12 PMroy_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