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

I am having difficulty understanding the Big-Oh rules. For example , here is a question :

Find example of functions ( which are not negative ) $d(n),f(n),e(n),g(n)$ such that $d(n)$ is $O(f(n))$ and $e(n)$ is $O(g(n))$, but $d(n)-e(n)$ is not $O(f(n)-g(n))$.

can someone please explain how to solve such a problem?

share|cite|improve this question
up vote 1 down vote accepted

Let $f(n)=3n^2 + n$ and $g(n)=3n^2$.

Take $ d(n)= 2n^2= O(f(n)) $ and $e(n)=n^2= O(g(n))$ as $n \to \infty$.

However, $d(n)-e(n)=n^2$ whereas $f(n)-g(n)=n$.

Therefore, $d(n)-e(n)$ is not $O(f(n)-g(n))$ as $n \to \infty$.

share|cite|improve this answer
thanks , this is very clear and understandable – Andy M Jan 24 '13 at 7:25
you are welcome! – Ragnar Jan 24 '13 at 11:26

Try $d = n, e = 1, f = n, g =n$

share|cite|improve this answer

Make the highest-order terms in $f(n)$ and $g(n)$ cancel. For example, $d(n) = 2n$, $e(n) = f(n) = g(n) = n$.

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.