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.

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

3 Answers 3

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|improve this answer
    
thanks , this is very clear and understandable –  Andy M Jan 24 '13 at 7:25
    
you are welcome! –  беркай Jan 24 '13 at 11:26

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

share|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|improve this answer

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.