 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2014/discrete-mathematics-continuous-mathematics-and-probability/3/d/solution

K

is fixed. By Big O notation, for each

i

there are constants

C_{i} > 0

and

N_{i}

such that

f_{i} (n) \leq C_{i} g (n)

when

n \geq N_{i}

. Take

N = max_{i} N_{i}

. For

n \geq N

, positivity gives

h (n) \leq (\sum_{i = 1}^{K} C_{i}) g (n), l (n) \leq (\sum_{i = 1}^{K - 1} C_{i} C_{i + 1}) g (n)^{2} .

The constants in parentheses are independent of

n

, proving

h = O (g), l = O (g^{2})

. If

K = 1

, the second sum is empty and

l = 0

, which satisfies the same upper bound.

 New to topics? Read the docs here!