Ratios of Big O

52 Views Asked by At

Consider two functions $f(n) = C_1 + O(1/n)$ and $g(n) = C_2 + O(1/n)$ where $C_1$ and $C_2$ are two non-zero constants.

Is is true that

$$\frac{f(n)}{g(n)} = \frac{C_1 + O(1/n)}{C_2 + O(1/n)} = (?) \frac{C_1}{C_2} + O(1/n)? $$

Imagine that I multiply everything by $C_2/C_2$, I obtain

$$\frac{f(n)}{g(n)} \frac{C_2}{C_2} = \frac{C_1/C_2 + O(1/n)}{1 + O(1/n)} = (?) \frac{C_1}{C_2} + O(1/n)? $$

We need to prove that there exist an $n_0$ and a positive constant $M_0$ such that for all $n \geq n_0$, we have that

$$\mid f(n)/g(n) \mid \leq C_1/C_2 + M_0 1/n$$

We know that there exists two constants $M_1$ and $M_2$ as well as two n's $n_1$ and $n_2$ such as

$$|f(n)| \leq C_1 + M_1 1/n, \quad \forall n \geq n_1 $$ $$|g(n)| \leq C_2 + M_2 1/n, \quad \forall n \geq n_2 $$

It is true that for all $n_1 \geq n$

$$\frac{|f(n)|}{|g(n)|} \leq \frac{C_1 + M_1 1/n}{|g(n)|} = \frac{C_1}{|g(n)|} + M_1 1/n/g(n)$$

but then we cannot say something since g(n) can be $< 1$ or $> 1$ ?

1

There are 1 best solutions below

0
On

By definition

$$h(n)=O\left(\frac1n\right) \iff h(n)=\frac{\omega(n)}{n}$$

with $\omega(n)$ bounded as $n \to \infty$ then for $g(n)\neq 0$ (at least eventually)

$$\frac{f(n)}{g(n)} = \frac{C_1 + O\left(\frac1n\right)}{C_2 + O\left(\frac1n\right)} = \frac{C_1 }{C_2 }+\left(\frac{C_1 + O\left(\frac1n\right)}{C_2 + O\left(\frac1n\right)}-\frac{C_1 }{C_2 }\right)=\frac{C_1 }{C_2 }+h(n)$$

with

$$h(n)=\left(\frac{C_1 + O\left(\frac1n\right)}{C_2 + O\left(\frac1n\right)}-\frac{C_1 }{C_2 }\right) =\frac{C_1C_2 + C_2O\left(\frac1n\right)-C_1C_2-C_1O\left(\frac1n\right)}{C_2\left(C_2 + O\left(\frac1n\right)\right)}=$$

$$=\frac{ (C_2-C_1)O\left(\frac1n\right) }{C_2\left(C_2 + O\left(\frac1n\right)\right)}=\frac{\frac{ (C_2-C_1)\omega(n) }{C_2\left(C_2 + O\left(\frac1n\right)\right)}}{n}=\frac{\Omega(n)}{n}=O\left(\frac1n\right)$$

since $\Omega(n)=\frac{ (C_2-C_1)\omega(n) }{C_2\left(C_2 + O\left(\frac1n\right)\right)}$ is bounded.