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

The relation is reflexive because $a-a=2\cdot 0$. It is symmetric because $a-b=2k$ implies $b-a=2(-k)$. It is transitive because $a-b=2k$ and $b-c=2\ell$ imply $a-c=2(k+\ell )$. It is therefore an equivalence relation, namely congruence modulo an integer for modulus two. Its two equivalence classes consist of the even integers and the odd integers.

The notation means that $n$ divides $a_1-a_2$:This is congruence modulo an integer; equivalently, the two integers have the same remainder on division by the positive integer $n$.

Write $a_1-a_2=kn$ with $k\in \mathbb{Z}$. The difference of two squares factors asThe final factor is an integer, so $n$ divides the difference. By congruence modulo an integer, $\boxed{a_1^2\equiv a_2^2(\mathrm{mod}n)}$.

Dividing by $n^2$ gives $10^5/n+2\to 2$. Thus the quadratic term controls the growth:The sharper Big theta notation also supplies the requested Big O notation bound.

For $n>0$,Consequently $\boxed{\sqrt{n^6+n^2}=\Theta (n^3),\text{in particular }O(n^3)}$ in Big theta notation and Big O notation.

Here $a,b\ge 2$ are fixed integers. The term $a{b}^n$ has exponential growth, whereas $a{n}^b$ has fixed-degree polynomial growth and $n{b}^a$ is linear. Since a fixed-base exponential eventually dominates every fixed-degree polynomial,Hence the requested Big O notation bound, with its matching lower order, is $\boxed{\Theta (b^n),\text{in particular }O(b^n)}$.

For sufficiently large positive $n$, the logarithm identities giveAfter division by $n{\log }_{2}n$, the right-hand side tends to one. Thus $\boxed{\Theta (n\log n),\text{in particular }O(n\log n)}$ gives the asymptotic order in Big theta notation and Big O notation.

The number $K$ is fixed. By Big O notation, for each $i$ there are constants $C_i>0$ and $N_i$ such that $f_i(n)\le C_{i}g(n)$ when $n\ge N_i$. Take $N={\max }_i{N}_i$. For $n\ge N$, positivity givesThe constants in parentheses are independent of $n$, proving $\boxed{h=O(g),l=O(g^2)}$. If $K=1$, the second sum is empty and $l=0$, which satisfies the same upper bound.

The printed fractional arguments require a size convention. To make the recurrence relation precise on positive integers, take a bounded base case $T(1)=t>0$ and use $m=\lceil n/4\rceil$, $n-m$ for $n\ge 2$. This integer rounding in a divide-and-conquer recurrence gives $1/4\le m/n\le 1/2$. The unrounded calculation is the special split fraction $1/4$.

Prove $T(n)\le An{\log }_{2}n+Bn$ by strong induction. Put $h_0=H_2(1/4)>0$, choose $A\ge 1/h_0$, and choose $B\ge t$. The base case follows. The entropy potential for a divide-and-conquer recurrence givesThe last step uses $H_2(m/n)\ge h_0$. This closes the inductive hypothesis and proves $\boxed{T(n)=O(n\log n)}$ in Big O notation.

Use the same integer rounding in a divide-and-conquer recurrence, now with root cost $n^2$. Since $1/4\le m/n\le 1/2$,Choose $C\ge \max \{T(1),8/3\}$ and use strong induction with inductive hypothesis $T(j)\le C{j}^2$. Both child sizes are positive and less than $n$, soThe same factor $5/8$ occurs for the exact fractional split. Therefore $\boxed{T(n)=O(n^2)}$ in Big O notation.