-----------------------------------

DaVe g

Fri Jan 16, 2009 10:02 am


Big Oh Question

-----------------------------------

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

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

Fri Jan 16, 2009 10:16 am


Re: Big Oh Question

-----------------------------------

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

Sat Jan 17, 2009 3:31 am


Re: Big Oh Question

-----------------------------------

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.