Question

​ For the function f defined by f(n) =n2+ 1/n+ 1 for n∈N, show that f(n)∈Θ(n). Use

Answer 1

$f(n)=\dfrac{n^2+1}{n+1}\leq\dfrac{n^2+n}{n+1}=n, n\in \N$

$\N=\{1,2,...\}$

By the definition $f(n)$ is $O(n)$ with $C=1$ and $k=1.$

$$\dfrac{n^2+1}{n+1}-\dfrac{n}{2}=\dfrac{2n^2+2-n^2-n}{2(n+1)}=$$

$$=\dfrac{n^2-n+\dfrac{1}{4}+\dfrac{7}{4}}{2(n+1)}=\dfrac{(n-\dfrac{1}{2})^2+\dfrac{7}{4}}{2(n+1)}>0,n\in\N$$

$$|f(n|)=|\dfrac{n^2+1}{n+1}|>\dfrac{1}{2} |n|, n\in\N$$

Then $f(n)$ is $\Omega(n).$

$$\dfrac{1}{2}|n|<|f(n)|\leq|n|, n\in\N$$

By the definition this means that $f(n)=\dfrac{n^2+1}{n+1}$ is $\Theta(n), n\in\N.$