1
$\begingroup$

I need help figuring out how to prove the following statement using the definition of "Big-Oh" notation which says that f ~ g if there are constants C and n_0 such that f(n) <= C*g(n), for n >= n_0. I have down below shared my attempts but am quite unsure about everything. For all I know I am not doing this correctly.

Statement 1: If f(n) ∈ O(f'(n)) and g(n) ∈ O(g'(n)), then f(n)g(n) ∈ O(f'(n)g'(n))

I can start by qouting the definition. We want to prove that f(n)g(n) ∈ O(f'(n)g'(n)) which means that f(n)g(n) <= Cj(n) ∀ n ≥ n_0 where j(n) is the order of growth is true for some constants C and n_0.

We are given that f(n) ∈ O(f'(n)) => f(n) <= C_1 * f'(n) and that g(n) ∈ O(g'(n)) => g(n) <= C_2 * g'(n). Using this information it must be true that f(n)g(n) <= C_1*f'(n) * C_2*g'(n) = Cf'(n)g'(n) => f(n)g(n) ∈ O(f'(n)g'(n)). Have I proven statement 1?

$\endgroup$
2

0

Browse other questions tagged or ask your own question.