The complexity analysis of the EuclidianEuclidean algorithm is much much older that the given reference. It goes back to at least LameLamé, before 1785. The above answerabove answer should be viewed as modern version of Lame'sLamé's theorem. The average is actually a normal variable, there are several difficult proofs, see Morris, arxiv.1502.07616Morris - A short proof that the number of division steps in the Euclidean algorithm is normally distributed, and earlier references.