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)>Cg(n)$, contradicting the required bound. The behavior on even integers cannot repair this failure on an unbounded subsequence.