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:

Given:

• 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)}).

Proof:

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.

OR