Big Oh Question

[DaVe g]

I'm having some troubles grasping this concept of the following question:

Quote:

Find an example of functions 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)). You don't have to prove anything for
this problem.

if d(n) is O(n^3) and e(n) is O(n^2), then the result for both d(n) - e(n) and O(f(n)-g(n)) is O(n), right?

I can't think of an example of two functions that would not be the same for both subtractions.

If anyone could shed a bit of light on this subject, I'd greatly appreciate it.

[Tony]

DaVe g @ Fri Jan 16, 2009 10:02 am wrote:

if d(n) is O(n^3) and e(n) is O(n^2), then the result for both d(n) - e(n) and O(f(n)-g(n)) is O(n), right?

No. The question asks for examples of 4 functions, and you provide none.

[Brightguy]

DaVe g @ Fri Jan 16, 2009 10:02 am wrote:

if d(n) is O(n^3) and e(n) is O(n^2), then the result for both d(n) - e(n) and O(f(n)-g(n)) is O(n), right?

No... did you mean division instead of subtraction?

The gist of it is that you want cancellation in f(n) - g(n) but not in d(n) - e(n). The cheap way is to let f(n) = g(n) and d(n) != e(n) for arbitrarily large n.