Prove the following theorem

4] Prove the following theorem if  t1(n) ϵO((g1(n)) and t2(n) ϵ O(g2(n)) then t1(n)+ t2(n) ϵ O(max{g1(n),g2(n})

To prove the theorem, we’ll use the definitions of Big O notation and the properties of the maximum function. Let’s break down the proof step by step:


  • t1(n) ∈ O(g1(n)), which means there exist constants c1 and n1 such that t1(n) ≤ c1 * g1(n) for all n ≥ n1.
  • t2(n) ∈ O(g2(n)), which means there exist constants c2 and n2 such that t2(n) ≤ c2 * g2(n) for all n ≥ n2.

We want to prove:

  • t1(n) + t2(n) ∈ O(max{g1(n), g2(n)}).


  1. First, let’s define M = max{g1(n), g2(n)}. So, M = max{g1(n), g2(n)}.
  2. We need to show that there exist constants c and n0 such that t1(n) + t2(n) ≤ c * M for all n ≥ n0.
  3. Using the properties of max{}, we can say that M ≥ g1(n) and M ≥ g2(n) for all n.
  4. Now, let’s consider t1(n) + t2(n): t1(n) + t2(n) ≤ c1 * g1(n) + c2 * g2(n) (Using the definitions of t1(n) and t2(n))
  5. Since M ≥ g1(n) and M ≥ g2(n) for all n, we can write: c1 * g1(n) ≤ c1 * M
    c2 * g2(n) ≤ c2 * M
  6. Therefore, we can combine the inequalities from step 5 with the inequality from step 4: t1(n) + t2(n) ≤ c1 * M + c2 * M
  7. Combining the constants c1 and c2, we get a new constant c = c1 + c2: t1(n) + t2(n) ≤ (c1 + c2) * M
  8. Now, we have shown that t1(n) + t2(n) is bounded by a constant times M, where M = max{g1(n), g2(n)}. Therefore, we have proved that t1(n) + t2(n) ∈ O(max{g1(n), g2(n)}), and the theorem is proven.


t1(n)+ t2(n) ϵ O(max{g1(n),g2(n})
t1(n)+ t2(n) ϵ O(max{g1(n),g2(n})

Leave a Reply

Your email address will not be published. Required fields are marked *