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

True. For every integer $n\ge 1$, $n^2\le n^3$ and $1\le n^3$. ThereforeThe constants $C=1097$ and $N=1$ satisfy the definition of Big O notation. Whether the chosen convention for natural numbers includes zero is immaterial to this eventual assertion.

False. Put $r_n=3^n/n^3$ for $n\ge 1$. For $n\ge 4$,Thus $r_n\ge r_4(192/125{)}^{n-4}\to \infty$. No fixed constant can bound $3^n/n^3$ eventually, so $3^n\ne O(n^3)$. This is an explicit comparison of exponential growth with polynomial growth.

True. Rationalization gives, for $n\ge 1$,This lies between zero and $1/4$, so it is $O(1)$ in Big O notation. In fact it converges to $1/4$, rather than to zero. The rationalized form also avoids the catastrophic cancellation of subtracting two nearby large quantities.

True for every fixed $k\ge 0$. Extract $e^n$ from inside the logarithm:Choose an integer $m>k$. The nonnegative terms of the exponential series give $e^n\ge n^m/m!$ for $n>0$, whenceSince $0\le \log (1+u)\le u$ for $u\ge 0$, the displayed expression tends to zero and is therefore $O(1)$. The constant and cutoff may depend on the fixed $k$; no uniform assertion over unbounded $k$ is being made.

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.