Question

a) Show that if f (x) and g(x) are functions such that f (x) is o(g(x)) and c is a constant, then cf (x) is o(g(x)), where (cf )(x) = cf (x).

b) Show that if${\mathit{f}}_{\mathbf{1}}\mathbf{\left(}\mathit{x}\mathbf{\right)}\mathbf{,}{\mathit{f}}_{\mathbf{2}}\mathbf{\left(}\mathit{x}\mathbf{\right)}$ and g(x) are functions such that ${\mathit{f}}_{\mathbf{1}}\mathbf{\left(}\mathit{x}\mathbf{\right)}$ is o(g(x)) and ${\mathit{f}}_{\mathbf{2}}\mathbf{\left(}\mathit{x}\mathbf{\right)}$is o(g(x)), then$\left(f_1+f_2\right)\mathbf{\left(}\mathit{x}\mathbf{\right)}$is o(g(x)), where$\left(f_1+f_2\right)\mathbf{\left(}\mathit{x}\mathbf{\right)}\mathbf{=}{\mathit{f}}_{\mathbf{1}}\mathbf{\left(}\mathit{x}\mathbf{\right)}\mathbf{+}{\mathit{f}}_{\mathbf{2}}\mathbf{\left(}\mathit{x}\mathbf{\right)}$

Short answer

We have to prove the definition of little o notations i.e,$\underset{n\to \mathrm{\infty }}{lim} \frac{f\left(n\right)}{g\left(n\right)}=0$

Step-by-step solution

Subpart (a): Show that if f (x) and g(x) are functions such that f (x) is o(g(x)) and c is a constant, then cf (x) is o(g(x)), where (cf )(x) = cf (x).Step 1:

Our functions are (cf)(x)=cf(x) and g(x)

We know that$\underset{x\to \mathrm{\infty }}{lim} \frac{f\left(x\right)}{g\left(x\right)}=0$

Determining the limit ratios of the functions:

$\underset{x\to \mathrm{\infty }}{lim} \frac{\left(cf\right)\left(x\right)}{g\left(x\right)}=\underset{x\to \mathrm{\infty }}{lim} \frac{cf\left(x\right)}{g\left(x\right)}=c\underset{x\to \mathrm{\infty }}{lim} \frac{f\left(x\right)}{g\left(x\right)}$

Step 2:

Since, $\underset{x\to \mathrm{\infty }}{lim} \frac{f\left(x\right)}{g\left(x\right)}=0$

$\underset{x\to \mathrm{\infty }}{lim} \frac{cf\left(x\right)}{g\left(x\right)}=c\underset{x\to \mathrm{\infty }}{lim} \frac{f\left(x\right)}{g\left(x\right)}=c.\left(0\right)=0$

Therefore, cf(x) is o(g(x)).

Subpart (b):

Show that if$f_1\left(x\right),f_2\left(x\right)$ , and g(x) are functions such that$f_1\left(x\right)$ is o(g(x)) and $f_2\left(x\right)$is o(g(x)), then$\left(f_1+f_2\right)\left(x\right)$ is o(g(x)), where$\left(f_1+f_2\right)\left(x\right)=f_1\left(x\right)+f_2\left(x\right)$

Step 4:

Our functions are $\left(f_1+f_2\right)\left(\mathrm{x}\right)=f_1\left(\mathrm{x}\right)+f_2\left(\mathrm{x}\right)$and g(x).

We know that $\underset{x\to \mathrm{\infty }}{lim} \frac{f\left(x\right)}{g\left(x\right)}=0$.

Determining the limit ratios of the functions:

$\underset{x\to \mathrm{\infty }}{lim} \frac{\left(f+f_2\right)\left(x\right)}{g\left(x\right)}=\underset{x\to \mathrm{\infty }}{lim} \frac{f_1\left(x\right)+f_2\left(x\right)}{g\left(x\right)}$

Step 5:

Since,$\underset{x\to \mathrm{\infty }}{lim} \frac{f\left(x\right)}{g\left(x\right)}=0$

$\underset{x\to \mathrm{\infty }}{lim} \left(\frac{f\left(x\right)}{\frac{1}{g\left(x\right)}}+\frac{2}{g\left(x\right)}\right)=\underset{x\to \mathrm{\infty }}{lim} \left(\frac{f\left(x\right)}{g\left(x\right)}\right)+\underset{x\to \mathrm{\infty }}{lim} \left(\frac{f\left(x\right)}{g\left(x\right)}\right)=0+0=0$

Therefore, $\left(\begin{array}{l}{f}_1+f_2\end{array}\right)\left(x\right)$is o(g(x))