0
$\begingroup$

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

  • 0
    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. @templatetypedef2012-02-08
  • 0
    Hi Allan Jiang.2014-04-21
  • 0
    @SandeepSilwal, the current accepted answer is completely correct. What kind of answer are you looking for with the bounty?2014-04-21
  • 0
    One that satisfies Allan Jiang.2014-04-21
  • 0
    @SandeepSilwal, if Allan Jiang would say how that answer does not satisfy him then a more appropriate one could be given.2014-04-21
  • 0
    No problem. :D ..2014-04-22

2 Answers 2

3

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.

  • 4
    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.2012-02-08
  • 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.2012-02-08
  • 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. :)2012-02-08
3

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!