-1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ What did you try? Where did you get stuck? Did you check the definitions of $O(-)$ and $\Omega(-)$? $\endgroup$ Commented Aug 14, 2015 at 14:37
  • $\begingroup$ @DavidRicherby I want to check if my way of using these notions is correct. I have doubt. $\endgroup$
    – user7060
    Commented Aug 14, 2015 at 14:42
  • $\begingroup$ If you have a doubt, try to prove your claim. $\endgroup$ Commented Aug 14, 2015 at 15:17

1 Answer 1

1
$\begingroup$

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)$.

$\endgroup$
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.