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

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.