Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability / 3 / e

Since $h(n)=\max \{f(n),g(n)\}$, both $f(n)\le h(n)$ and $g(n)\le h(n)$. Therefore $f(n)+g(n)\le 2h(n)$ for every positive $n$. The definition of big O notation is satisfied with constant $2$ and threshold $1$. True: $f+g=O(h)$.

Positivity gives $\max \{f(n),g(n)\}\le f(n)+g(n)$. Thus $h(n)\le f(n)+g(n)$ for every positive $n$, meeting big O notation with constant $1$ and threshold $1$. True: $h=O(f+g)$.

Take $f(n)=g(n)=n^2$, so $h(n)=n^2$ but $(f\circ g)(n)=n^4$. The ratio $(f\circ g)(n)/h(n)=n^2$ is unbounded, precluding any eventual constant upper bound in big O notation. False: in general $f\circ g\ne O(h)$. This is a counterexample involving function composition, not pointwise addition.

For each fixed positive integer $k$, part (i) gives $(f(n)+g(n){)}^k\le (2h(n){)}^k=2^{k}h(n{)}^k$. This meets big O notation with constant $2^k$ and threshold $1$. True: $(f+g{)}^k=O(h^k)$ for fixed $k$. The constant may depend on $k$; no claim uniform in a varying $k$ is required.