Rule of Sums

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