 Home

Codex Wiki

List of universities

University of Oxford

Course of the University of Oxford

Undergraduate course of the University of Oxford

Computer science course of the University of Oxford

Year 1 of the computer science course of the University of Oxford

Past exam of the year 1 of the computer science course of the University of Oxford

2013

Discrete mathematics, probability and continuous mathematics

By <Big O notation>, there are $C_1,C_2>0$ and thresholds after which $f_1(n)\leq C_1g_1(n)$ and $f_2(n)\leq C_2g_2(n)$. Choose a common threshold and set $C=\max(C_1,C_2)$. The positivity assumption gives
$$
0\leq f_1(n)+f_2(n)\leq C(g_1(n)+g_2(n)).
$$
Squaring preserves this inequality, so
$$
\boxed{(f_1+f_2)^2\leq C^2(g_1+g_2)^2\text{ eventually},\qquad(f_1+f_2)^2=O((g_1+g_2)^2).}
$$

Solution

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

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

 Ancestors (12)

 Discussion (0) New discussion

 Articles by others on the same topic (0)

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

 Ancestors (12)

 Discussion (0)  Subscribe (1) New discussion

 Articles by others on the same topic (0)

 Discussion (0) New discussion