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
    No $p$roblem. :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.

  • 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!