Answer to Question #138253 in Discrete Mathematics for sara

Question #138253
​ For the function f defined by f(n) =n2+ 1/n+ 1 for n∈N, show that f(n)∈Θ(n). Use
1
Expert's answer
2020-10-14T18:24:16-0400

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

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

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



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

=n2n+14+742(n+1)=(n12)2+742(n+1)>0,nN=\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)=n2+1n+1>12n,nN|f(n|)=|\dfrac{n^2+1}{n+1}|>\dfrac{1}{2} |n|, n\in\N

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

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

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




Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment