Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

migrated from stackoverflow.com 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 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 at 14:16
    
One that satisfies Allan Jiang. –  Sandeep Silwal Apr 21 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 at 15:11
show 2 more comments

2 Answers

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|improve this answer
3  
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
1  
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
2  
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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.