Computer Science Canada Big Oh Question |
| Author: | DaVe g [ Fri Jan 16, 2009 10:02 am ] |
| Post subject: | Big Oh Question |
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. |
|
| Author: | Tony [ Fri Jan 16, 2009 10:16 am ] |
| Post subject: | Re: Big Oh Question |
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. |
|
| Author: | Brightguy [ Sat Jan 17, 2009 3:31 am ] |
| Post subject: | Re: Big Oh Question |
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. |
|