Comp Sci Time Complexity Algorithm Proof

[enigmatic01]

Homework Statement

Use the formal definition of Big-Oh to prove that if f (n) and g(n) are nonnegative functions such that f (n) = O(g(n)), f (n) + g(n) = Ω(g(n))

Relevant Equations

...

Use the formal definition of Big-Oh to prove that if f (n) and g(n) are nonnegative functions such that f (n) = O(g(n)), f (n) + g(n) = Ω(g(n)).

By the definition of Big-Oh:

If f(n) and g(n) are non-negative functions such that f(n) = O(g(n)) there must be positive constants c and n0 such that 0 ≤ f(n) ≤ c(g(n)) for all n ≥ n0

Would this be correct:

If 0 ≤ f(n) ≤ c(g(n)) and f(n) and g(n) are non-negative functions we know g(n) ≤ ( f(n) + g(n) ).

Since g(n) ≤ f(n) + g(n) there must be a constant c, namely 0 < c ≤ 1, such that c(g(n) ≤ g(n). We could then say 0 ≤ c(g(n)) ≤ f(n) + g(n) which is the definition of f (n) + g(n) = Ω(g(n))

 

[mfb]

That doesn't even use f(n) = O(g(n)) but it looks correct (assuming you use Knuth's definition of Ω).

A more interesting result to show (one that needs f(n) = O(g(n))) would be f (n) + g(n) = O(g(n))

 

[enigmatic01]

That doesn't even use f(n) = O(g(n)) but it looks correct (assuming you use Knuth's definition of Ω).

A more interesting result to show (one that needs f(n) = O(g(n))) would be f (n) + g(n) = O(g(n))

That was actually the other homework problem!