All pastes #899321 Raw Edit

k4st

public text v1 · immutable
·published 2008-02-11 01:15 UTC
rendered paste body

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

R-4.23) show that if d(n) is O(f(n)) and e(n) is O(g(n)) 
        then d(n) - e(n) is not necessarily O(f(n) - g(n))

Example for when d(n) - e(n) is O(f(n) - g(n))
d(n) = 2n + 3
e(n) = 2n + 5

f(n) = 2n + 3n = 5n. C = 5, O(g(n)) is O(n)
g(n) = 2n + 5n = 7n. C = 7, O(g(n)) is O(n)

(2n + 3) - (2n + 5) is O(n - n)
-2 is O(1)

Example for when d(n) - e(n) is not O(f(n) - g(n))

d(n) = 10n
e(n) = n

d(n) is O(n)
e(n) is O(n)

d(n) - e(n) is? O(n - n)
10n - n is? O(1)
O(n) is not O(1)