f(n)=n+1n2+1≤n+1n2+n=n,n∈N
N={1,2,...}
By the definition f(n) is O(n) with C=1 and k=1.
n+1n2+1−2n=2(n+1)2n2+2−n2−n=
=2(n+1)n2−n+41+47=2(n+1)(n−21)2+47>0,n∈N
∣f(n∣)=∣n+1n2+1∣>21∣n∣,n∈N Then f(n) is Ω(n).
21∣n∣<∣f(n)∣≤∣n∣,n∈N By the definition this means that f(n)=n+1n2+1 is Θ(n),n∈N.
Comments
Leave a comment