 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2019/discrete-mathematics-continuous-mathematics-and-probability-resit/3/a/v/solution

False. On every odd positive integer

n

f (n) / g (n) = n

. Given any proposed Big O notation constant

C

and threshold

N

, choose an odd

n > max (C, N)

. Then

f (n) > C g (n)

, contradicting the required bound. The behavior on even integers cannot repair this failure on an unbounded subsequence.

 New to topics? Read the docs here!