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

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.

The prime numbers $2,3,5$ form the lower antichain; the nonprime elements $1,4$ form the upper antichain. In particular, $1$ is not a prime number. Each lower element is below each upper element, and no third element can lie strictly between them. Therefore the six cover relations are $2,3,5\prec 1,4$, represented by the following Hasse diagram. Upward movement represents increasing order; crossing lines do not add elements.

Write $P$ for the prime numbers in $A$ and $C=A\setminus P$ for its nonprime elements. Since $n\ge 4$, both antichains have at least two elements: $2,3\in P$ and $1,4\in C$. Every element of $P$ is below every element of $C$. We can classify a subset $S$ by its intersection with these two levels of the two-level partial order.

Consequently an upper bound exists exactly when $|S\cap C|\le 1$; a maximum or least upper bound exists exactly when $|S\cap C|=1$ or $S$ is a singleton subset of $P$. The exhaustive cases also justify why the last two existence criteria coincide here.