Proving this Statement

Question

Use the definition of Big-Oh to prove that following statement:

Suppose T1(N) = O(f(N)) and T2(N) = O(f(N)), T1(N) + T2(N) = O(f(N))

Answer 1

When we suppose that T1 is O(f), we get a constant C1 and a number N1 such that for n>N1, T1(n) < C1*f(n)

Likewise we get a constant C2 and a number N2 such that for n>N2, T2(n) < C2*f(n)

Thus we can take our new constant to be C1+C2, and our new number to be max(N1, N2), and this should satisfy the definition. I'll leave it to you to work out the specifics of why this is true.