The Computing Time of the Euclidean Algorithm
George Ernest Collins · SIAM Journal on Computing · 1974
The minimum, maximum and average computing times of the classical Euclidean algorithm are derived. With positive integer inputs of lengths m and n, and with output (greatest common divisor) of length k, $m \geqq n \geqq k$, the minimum is shown to be codominant with $n(m - n + 1) + k(n - k + 1)$, while both the maximum and the average are shown to be codominant with $n(m - k + 1)$.