Question

a.) State the definition of the fact that f(n)is $\mathit{O}\mathbf{\left(}\mathit{g}\mathbf{\right(}\mathit{n}\mathbf{\left)}\mathbf{\right)}$, where $\mathit{f}\mathbf{\left(}\mathit{n}\mathbf{\right)}$ and$\mathbf{g}\mathbf{\left(}\mathbf{n}\mathbf{\right)}$ are functions from the set of positive integers to the set of real numbers.

b.) Use the definition of the fact that f(n)is$\mathbf{O}\mathbf{\left(}\mathbf{g}\mathbf{\right(}\mathbf{n}\mathbf{\left)}\mathbf{\right)}$directly to prove or disprove that ${\mathbf{n}}^{\mathbf{2}}\mathbf{+}\mathbf{18}\mathbf{n}\mathbf{+}\mathbf{107}$is $\mathit{O}\mathbf{\left(}{\mathit{n}}^{\mathbf{3}}\mathbf{\right)}$.

c.) Use the definition of the fact that f(n)is$\mathit{O}\mathbf{\left(}\mathit{g}\mathbf{\right(}\mathit{n}\mathbf{\left)}\mathbf{\right)}$directly to prove or disprove that${\mathit{n}}^{\mathbf{3}}$is$\mathit{O}\mathbf{(}{\mathit{n}}^{\mathbf{2}}\mathbf{+}\mathbf{18}\mathit{n}\mathbf{+}\mathbf{107}\mathbf{)}$.

Short answer

a.) f(x) is $O\left(g\right(x\left)\right)$ if there exists constants and such that$\left|f\right(x\left)\right|\le C\left|g\right(x\left)\right|$ whenever$x>k$

b.) $n^2+18n+107$is$O\left(n^3\right)$.

c.) $n^3$is not $O(n^2+18n+107)$

Step-by-step solution

(a)Step 1: State the definition of the fact that f(n) is  O(g(n)), where f(n)  and g(n) are functions from the set of positive integers to the set of real numbers

Big-O Notation: $f\left(x\right)$ is $O\left(g\right(x\left)\right)$if there exists constants and such that

$\left|f\right(x\left)\right|\le C\left|g\right(x\left)\right|$

whenever $x>k$

(b)Step 2: Prove or disprove that n2+18n+107 is O(n3)

Let us assume $k=107$. For $n>k$, we then obatain:

$|n^2+18n+107|=n^2+18n+107$

$$\begin{gathered} \le n^2+n\cdot n+n \\ =n^2+n^2+n \\ =2n^2+n \\ =2n^2+n\cdot 1 \\ <2n^2+n\cdot n \\ =2n^2+n^2 \\ =3n^2 \\ <3n^2 \\ =3\left|n^3\right| \end{gathered}$$

We then need to take atleast C.Thus let us take $C=3$.

By the definition of the Big- notation, we have then shown that$n^2+18n+107$ is$O\left(n^3\right)$ with $k=107$ and$C=3$

(c)Step 3: Prove or disprove that n3  is O(n2+18n+107)

PROOF BY CONTRADICTION

Let us assume that $n^3$is $O(n^2+18n+107)$. Then there exists constants k and C such that

$\left|n^3\right|\le C|n^2+18n+107|$

whenever $n>k$

Since k is a lower bound for the -values, we can assume that k is atleast 1 without loss of generality (because if the statement is true for $k<1$, the it will also be true for any value of k that is at least 1 )

$k\ge 1$

Since $n>k\ge 1$, we then obtain:

$\left|n^3\right|\le C|n^2+18n+107|\le C|n^2+18n^2+107n^2|=C\left|126n^2\right|=126C\left|n^2\right|$

Dividing both side of the inequality by $n^2$, we then obtain:

$\left|n\right|<126C$

$n^3$is not $O(n^2+18n+107)$