1
$\begingroup$

Say that $f(n) = \cal O(n^2)$ and $g(n) = \cal O(n)$.

If $h(n)=f(n)/g(n)$, is it true that $h(n) =\cal O(n)$?

Is it mathematically correct to say that $h(n) = \cal O(n^2)/ O(n) = O(n)$? if not, what would be the correct way to show this?

$\endgroup$
  • 2
    $\begingroup$ Hence we see why you should always use $\Theta$ when you mean it. $\endgroup$ – Raphael Apr 14 '14 at 7:55
  • $\begingroup$ This is a dump of an exercise problem, not a question. If you have a specific question regarding the wording of the problem or concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See also here for our homework policy, and here for a relevant discussion. You may also want to check out our reference questions. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – D.W. Apr 15 '14 at 18:20
9
$\begingroup$

Let $f(n)= n^2$ and $g(n)=1$. Then $f(n) = \cal O(n^2)$ and $g(n) = \cal O(n)$.

However, $h(n)=f(n)/g(n)=n^2/1 = n^2 \neq \cal{O}(n)$.

$\endgroup$
  • $\begingroup$ For an even more extreme example, take $g(n)=n^{-1000000}\;$! $\endgroup$ – David Richerby Apr 14 '14 at 7:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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