Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 3

For these real-valued functions, $f(n)=O(g(n))$ means that there exist constants $C>0$ and $N\in \mathbb{N}$ such thatThe absolute values matter because neither function is assumed nonnegative. The constants are independent of $n$; finitely many earlier values do not affect Big O notation.

True. For every integer $n\ge 1$, $n^{3/2}\le n^2$ and $1\le n^2$, soThus $C=14$ and $N=1$ witness the required Big O notation bound.

False. Set $r_n=n!/2^n$. The ratio of successive terms isConsequently $r_n\ge r_3{2}^{n-3}$ for $n\ge 3$, which is unbounded. No constant can bound $n!$ by that constant times $2^n$ for all sufficiently large $n$. The factorial therefore fails the proposed Big O notation bound, without needing Stirling's formula.

True. Every term has $k^2\le n^2$ when $1\le k\le n$. Adding these $n$ inequalities givesThe constants $C=1$ and $N=1$ suffice in the definition of Big O notation.

False. The sum of squares of the first n positive integers givesThis ratio is unbounded, so it cannot satisfy the constant bound required by Big O notation. In fact the sum has order $n^3$, as its leading term also shows.

An element $u\in A$ is a least upper bound of $S$ if it is an upper bound, meaning $s\le u$ for every $s\in S$, and $u\le v$ for every upper bound $v\in A$ of $S$. The candidate need not belong to $S$. Because a partial order is an antisymmetric relation, two least upper bounds must be equal. A least upper bound is also called the supremum.

An element $m$ is a maximum of $S$ if $m\in S$ and $s\le m$ for every $s\in S$. Thus it is an upper bound that is itself a member. Every maximum is the least upper bound: any upper bound must lie above $m$ because $m\in S$. A supremum outside $S$ need not be a maximum.

Under the product order, every point of the open unit disc has both coordinates below one, so $(1,1)$ is an upper bound. Any upper bound $(u,v)$ must have $u\ge 1$ and $v\ge 1$, since the two coordinate projections of the open unit disc are $(-1,1)$. Therefore $(1,1){\le }_P(u,v)$, proving ${\sup }_{{\le }_P}S=(1,1)$.

Under the lexicographic order, every point $(1,v)$, with arbitrary real $v$, is an upper bound, because every point of $S$ has first coordinate strictly below one. Conversely, an upper bound cannot have first coordinate $u<1$: a point $(x,0)\in S$ with $x>u$ would exceed it. If an upper bound has $u>1$, the upper bound $(1,0)$ is strictly smaller. If it is $(1,v)$, the upper bound $(1,v-1)$ is strictly smaller. Hence there is no least upper bound under the lexicographic order. This illustrates the supremum of an open disc under product and lexicographic orders.