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

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.