Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Discrete mathematics, continuous mathematics and probability resit / 2 / c / v / Solution

False. On the unbounded subsequence of odd positive integers, $f(n)/g(n)=n$. For any proposed constants $C>0,N$, choose an odd $n>\max (C,N)$. Then $|f(n)|=n>C|g(n)|=C$, contradicting the eventual upper bound required by Big O notation. The small ratio on even integers cannot compensate for this failure on infinitely many odd integers.