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

As $x\to +\infty$, big O notation meansThe same constant must work on the entire sufficiently large tail. Absolute values accommodate signed functions. A two-sided convention at infinity would replace $x\ge x_0$ by $|x|\ge x_0$; the positive-integer arguments in the later parts use the positive-tail convention.

Choose constants $C_1,C_2>0$ and a common threshold beyond which $f_1\le C_1{g}_1$ and $f_2\le C_2{g}_2$. Positivity permits multiplication:The fixed constant $C_1{C}_2$ proves $f_1{f}_2=O(g_1{g}_2)$ by the definition of big O notation.

Beyond the same common threshold, the triangle inequality givesThus $f_1-f_2=O(g_1+g_2)$. The absolute value matters because the difference need not itself be positive, even though the four original functions are.

TakeThe premises hold with constants two and one. ButNo fixed bounding constant can satisfy the proposed conclusion. This proves the failure of unrestricted Big O composition: a constant factor in an inner argument can become an unbounded factor after applying an exponential.

A stronger exact formula makes the induction explicit:For $n=1$, the recurrence gives $S_1=S_0+m=1+m$. For $n\ge 2$, set $j=\lfloor n/2\rfloor$, so $1\le j<n$. In the relevant binary interval, $\lfloor {\log }_{2}j\rfloor =\lfloor {\log }_{2}n\rfloor -1$. The strong induction hypothesis givesFor $n\ge 2$, $S_n\le 1+m+m{\log }_{2}n\le (1+2m){\log }_{2}n$. Hence $S_n=O({\log }_{2}n)$. This is an integer-halving recurrence with constant toll; the separately defined $n=0$ case does not require evaluating $\log 0$.

A preorder is reflexive and transitive: $xRx$ for every element, and $xRy,yRz$ imply $xRz$. A partial order additionally requires antisymmetry: $xRy$ and $yRx$ imply $x=y$. It need not compare every pair of distinct elements.

No. On $\{0,1,2\}$ take $R=\{(0,1),(1,2),(2,0)\}$. This is an antisymmetric relation because it contains no opposite pair of distinct elements. Its reflexive transitive closure contains every ordered pair: following the directed three-cycle reaches any vertex from any other. In particular it contains both $(0,1)$ and $(1,0)$, violating antisymmetry.

This illustrates the reachability preorder: collapsing mutually reachable vertices into strongly connected components yields a partial order, but retaining all original vertices need not.