Cheap and Secure Web Hosting Provider : See Now

Use of Landau notation for determining bounds

, , No Comments
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.

Asked By : user7060
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)$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/45258

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback