 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2013/discrete-mathematics-probability-and-continuous-mathematics/2/c/solution

By Big O notation, there are

C_{1}, C_{2} > 0

and thresholds after which

f_{1} (n) \leq C_{1} g_{1} (n)

and

f_{2} (n) \leq C_{2} g_{2} (n)

. Choose a common threshold and set

C = max (C_{1}, C_{2})

0 \leq f_{1} (n) + f_{2} (n) \leq C (g_{1} (n) + g_{2} (n)) .

Squaring preserves this inequality, so

(f_{1} + f_{2})^{2} \leq C^{2} (g_{1} + g_{2})^{2} eventually, (f_{1} + f_{2})^{2} = O ((g_{1} + g_{2})^{2}) .

 New to topics? Read the docs here!