For two non-negative functions f and g, prove or disprove if f = O(g) and g = O(f) and ∀n,f(n) g(n) then f − g = O(1)

Question

I am a bit confused about how to utilize the asymptotic analysis to prove this statement. I've tried to use the definition of f = O(g) and g = O(f), namely 0 and 0,however I can deduce what will happen for f(n)-g(n). Can someone help me out on this?

user_3768871 · Answer

You can make a lot of counterexamples. A simple one is: f(n) = 2n and g(n) = n. You can see 2n \in O(n) and n \in O(2n) by definition. But, f(n) - g(n) = n that is obviously not in O(1).

For two non-negative functions f and g, prove or disprove if f = O(g) and g = O(f) and ∀n,f(n) > g(n) then f − g = O(1)

1 Answers