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

True. For every $n\ge 1$,These constants satisfy the definition of Big O notation.

False. Set $a_n=4^n/n^4$. For $n\ge 4$,Iteration gives a growing geometric sequence as a lower bound for $a_n$. Hence $a_n\to \infty$ and no eventual constant can bound $4^n/n^4$, as Big O notation would require.

True. Rationalizing the square root gives, for $n\ge 1$,The uniform bound is exactly the assertion $O(1)$ in Big O notation.

True. The logarithm identity givesFor $n\ge 1$, $e^n\ge n$, so $0\le n{e}^{-n}\le 1$. By monotonicity of the natural logarithm, the expression lies between $0$ and $\ln 2$. It is therefore $O(1)$ in Big O notation.

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.