Rule of Products

PROBLEM

Given:

• 𝑔₁(𝑛) = 𝑂(𝑓₁(𝑛))
• 𝑔₂(𝑛) = 𝑂(𝑓₂(𝑛))

Show that:

• 𝑔₁(𝑛)·𝑔₂(𝑛) = 𝑂(𝑓₁(𝑛)·𝑓₂(𝑛))

PROOF

• 𝑔₁(𝑛) ≤ 𝑐₁·𝑓₁(𝑛) for all 𝑛≥𝑛₁ # by definition of Big O notation
• 𝑔₂(𝑛) ≤ 𝑐₂·𝑓₂(𝑛) for all 𝑛≥𝑛₂ # by definition of Big O notation

Let:

• 𝑛₀ = 𝑚𝑎𝑥(𝑛₁, 𝑛₂)

Then, for all 𝑛≥𝑛₀:

• 𝑔₁(𝑛)·𝑔₂(𝑛) = 𝑐₁·𝑓₁(𝑛) · 𝑐₂·𝑓₂(𝑛)
• 𝑔₁(𝑛)·𝑔₂(𝑛) = 𝑐₁·𝑐₂·𝑓₁(𝑛)·𝑓₂(𝑛)
• 𝑔₁(𝑛)·𝑔₂(𝑛) = 𝑐·𝑓₁(𝑛)·𝑓₂(𝑛) # 𝑐 = 𝑐₁·𝑐₂
• 𝑔₁(𝑛)·𝑔₂(𝑛) = 𝑂(𝑓₁(𝑛)·𝑓₂(𝑛)) # by definition of Big O notation