CODEWITHSUNDEEP
time-complexitybig-o
Gil Dekel
Gil Dekel

Reputation: 365

Asymptotic notation and Growth of Combinations of Functions: Difference

I need to prove or disprove the following conjecture:

if f(n) = O(h(n)) AND g(n) = O(k(n)) then (f − g)(n) = O(h(n) − k(n))

I am aware of the sum and product theorems for growth combination, but I could not find a way to apply them here, even though I know that subtraction can be rewritten as addition. Everywhere I looked defined the mentioned theorems, but lacked examples of subtraction.

Upvotes: 0

Views: 438

Answers (1)

chiwangc
chiwangc

Reputation: 3577

Your statement is not true, consider the following counter-example:

Take f(n) = 2n2 = O(n2) and g(n) = n2 = O(n2). We have:

(f-g)(n) = n2, which is definitely not a constant and hence (f-g)(n) ≠ O(1).

Upvotes: 4

Related Questions