Question

Write a direct proof of the fact "O is closed under addition." That is, suppose two functions f and h are both O(g). Prove that the function f h is also O(g)

Answer 1

To prove that O is closed under addition, we need to show that if functions f and h are both O(g), then the function fh is also O(g). We can prove this by assuming that f(x) is less than or equal to a constant multiple of g(x), and h(x) is less than or equal to another constant multiple of g(x), and then using the properties of inequalities to show that fh(x) is also less than or equal to a constant multiple of g(x).

Step-by-step explanation:

To prove that O is closed under addition, we need to show that if functions f and h are both O(g), then the function fh is also O(g). Let's assume that f(x) ≤ c1g(x) and h(x) ≤ c2g(x) for all x ≥ k, where c1, c2, and k are constants. We want to find a constant c and a value k' such that fh(x) ≤ cg(x) for all x ≥ k'.

Using the properties of inequalities and the fact that g(x) > 0 for x ≥ k, we have:

1. fh(x) = f(x)h(x) ≤ c1g(x)c2g(x) = (c1c2)g(x)² for all x ≥ k
2. Let c = c1c2 and k' = k. Then, fh(x) ≤ cg(x) for all x ≥ k'.

This shows that fh(x) is also O(g(x)), and therefore, O is closed under addition.