# Ratios in big-O notation?

Hi can anyone give me a counter example of the following claim:

f(n) = O(s(n)) and g(n)=O(r(n)) imply f(n)/g(n) = O(s(n)/r(n))


Thank you

-

## migrated from stackoverflow.comFeb 8 '12 at 16:33

This question came from our site for professional and enthusiast programmers.

This is a question from my algorithm text book. So far I just assume there might be a way on the left side to cancel out the critical terms by dividing, but the right side can keep what ever it is. But I couldn't come up with a complete solution to it. @templatetypedef – Allan Jiang Feb 8 '12 at 5:27
Hi Allan Jiang. – Sandeep Silwal Apr 21 '14 at 5:41
@SandeepSilwal, the current accepted answer is completely correct. What kind of answer are you looking for with the bounty? – Antonio Vargas Apr 21 '14 at 14:16
One that satisfies Allan Jiang. – Sandeep Silwal Apr 21 '14 at 15:00
@SandeepSilwal, if Allan Jiang would say how that answer does not satisfy him then a more appropriate one could be given. – Antonio Vargas Apr 21 '14 at 15:11

It's easy.

Let f(n) = n^2 = O(n^2) and g(n) = n = O(n^2). And we get f(n)/g(n) = n which is not in the set O(n^2 / n^2) = O(1)

Why n=O(n^2) ? Because there exists a positive constant number M(=1) and a real number n_0(=2), such that |n|<=M|n^2|, for all x >x_0.

-
Given how clear it's been made that this is (a) a homework problem and (b) the OP hasn't made any apparent attempt to solve it themselves, rewarding their laziness by providing the answer is... unfortunate. – djacobson Feb 8 '12 at 5:48
I feel so sorry... I'm fresh here, and I just answered this question as soon as I saw it and I did not think more. – Rubbish_Oh Feb 8 '12 at 5:57
That's fair - and I apologize if my tone was harsh; this scenario just tends to happen a lot. Please don't be discouraged from contributing in future. :) – djacobson Feb 8 '12 at 5:58

As a hint, remember that big-O is not a tight bound. Could you make r(n) grow much more rapidly than g(n), such that O(s(n) / r(n)) ends up being much smaller than f(n) / g(n)?

Hope this helps!

-