 Solution

ID: 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/iv/solution

For each fixed positive integer

k

, part (i) gives

(f (n) + g (n))^{k} \leq (2 h (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.

 New to topics? Read the docs here!