Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

migrated from Feb 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
up vote 3 down vote accepted

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.

share|cite|improve this answer
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!

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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