#### 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:

- First, let’s define
**M = max{g1(n), g2(n)}.**So,**M = max{g1(n), g2(n)}.** - We need to show that there exist constants c and n0 such that
**t1(n) + t2(n) ≤ c * M**for all n ≥ n0. - Using the properties of max{}, we can say that M ≥ g1(n) and M ≥ g2(n) for all n.
- 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)) - Since M ≥ g1(n) and M ≥ g2(n) for all n, we can write:
**c1 * g1(n) ≤ c1 * M**

c2 * g2(n) ≤ c2 * M - Therefore, we can combine the inequalities from step 5 with the inequality from step 4:
**t1(n) + t2(n) ≤ c1 * M + c2 * M** - Combining the constants c1 and c2, we get a new constant
**c = c1 + c2: t1(n) + t2(n) ≤ (c1 + c2) * M** - 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.