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

For functions $f,g:\mathbb{N}\to \mathbb{R}$, big O notation meansUsing the natural logarithm and exponential function, $3^{\log n}=n^{\log 3}$. Since $\log 3>1$, for every $n\ge 1$ we have $n\le n^{\log 3}$. The witnesses $C=1,N=1$ therefore prove

For $n\ge 1$, $\log 3<2$ implies $3^{\log n}=n^{\log 3}\le n^2$, and also $n\le n^2$. ConsequentlyThe definition of big O notation holds with $C=4,N=1$:

Suppose the definition of big O notation held with constants $C>0,N$. Choose an odd integer $n>\max (C,N)$. At this input, $f(n)=n$ and $g(n)=1$, so the required inequality would be $n\le C$, a contradiction. ThusThe infinitely many even inputs, where $f(n)/g(n)=1/n$, cannot repair the failure on odd inputs because the bound must hold for every sufficiently large input.

A direct mathematical induction proves $0\le F_n\le 2^n$. The base cases $F_0=0\le 1$ and $F_1=1\le 2$ hold. If the bound holds at $n-1$ and $n$, then the Fibonacci recurrence givesThus the definition of big O notation holds with $C=1$, proving

By divisibility, write $a=nu$ and $b=nv$ for positive integers $u,v$. ThenThe factor $u^2-v^2$ is an integer, so

The Euclidean division gives $a=qb+r$ with $q\in {\mathbb{N}}_0$ and $0\le r<b$. Writing $a=nu,b=nv$ givesSince $u-qv$ is an integer, this proves the divisibilityincluding $r=0$.

The greatest common divisor is the largest positive integer dividing both inputs:This maximum exists because $1$ belongs to the set and all its elements are at most $b$.

Write $a=qb+r$ using the Euclidean division. If $d\mid a$ and $d\mid b$, then $d\mid (a-qb)=r$. Conversely, if $d\mid b$ and $d\mid r$, then $d\mid (qb+r)=a$. Therefore $(a,b)$ and $(b,r)$ have exactly the same positive common divisors, provingFor $r=0$, this agrees with $\gcd (b,0)=b$.

Set $(a_0,b_0)=(a,b)$. At each iteration with $b_i>0$, compute the remainder $r_i=a_i\mathrm{mod}{b}_i$, then setStop at the first index $n$ with $b_n=0$ and return $a_n$. The positive second coordinates strictly decrease, so algorithm termination follows from the well-ordering principle. The equality of greatest common divisors established in (ii) is a loop invariant, and at termination it gives

Consider one iteration with $a_i>b_i>0$ and $r_i=a_i\mathrm{mod}{b}_i$. If $b_i\le a_i/2$, then $r_i<b_i\le a_i/2$. If $b_i>a_i/2$, the quotient is $1$, so $r_i=a_i-b_i<a_i/2$. In either case $r_i<a_i/2$, whenceRepeated application, or mathematical induction, provesThis also holds for the final iteration, whose left side is zero. For zero iterations the correct relation is equality $a_0{b}_0=ab$, rather than a strict inequality.

Count the final division producing zero as an iteration, and let the total be $n$. The terminal product $a_n{b}_n=0$ alone gives no useful bound. Instead apply (i) to each nonterminal product, which is a positive integer and hence at least $1$.

If $n\ge 2$, the penultimate product satisfiesAs $n$ is an integer, this impliesFor $n=1$, the same bound holds since $a>b\ge 1$ implies $ab\ge 2$. In particular the Euclidean algorithm uses $O(\log a+\log b)$ divisions, in big O notation. The convention that includes the final zero-producing division explains the one-step offset in the argument.

The second coordinate after two iterations satisfieswhenever those two divisions are needed, by the same remainder bound, now applied to $b_i>b_{i+1}>0$. Let $m=\lfloor {\log }_{2}b\rfloor$. If the Euclidean algorithm has not already stopped after $2m$ iterations, then its positive second coordinate is at most $1$: for $m\ge 1$,For $m=0$ the original $b$ is already $1$. A second coordinate of $1$ requires just one more division. ConsequentlyThis removes dependence on the potentially much larger input $a$. It improves the scale ${\log }_2(ab)$ to one involving only the smaller input; the rounded numerical bound need not be smaller for every pair. One may always take the minimum of the bounds in (ii) and (iii).