World's most popular travel blog for travel bloggers.

# Use of Landau notation for determining bounds

, ,
Problem Detail:

Assume that we have $l \leq \frac{u}{v}$ and assume that $u=O(x^2)$ and $v=\Omega(x)$. Can we say that $l=O(x)$?

Thank you.

###### Answered By : Yuval Filmus

Since $u = O(x^2)$, there exist $N_1,C_1>0$ such that $u \leq C_1x^2$ for all $x \geq N_1$. Since $v = \Omega(x)$, there exist $N_2,C_2>0$ such that $v \geq C_2x$ for all $x \geq N_2$. Therefore for all $x \geq \max(N_1,N_2)$ we have $$l \leq \frac{u}{v} \leq \frac{C_1x^2}{C_2x} = \frac{C_1}{C_2} x.$$ So $l = O(x)$.