Euclidean Algorithm - Algorithmic Efficiency

Algorithmic Efficiency

The computational efficiency of Euclid's algorithm has been studied thoroughly. This efficiency can be described by the number of steps the algorithm requires, multiplied by the computational expense of each step. As shown first by Gabriel Lamé in 1844, the number of steps required for completion is never more than five times the number h of digits (base 10) of the smaller number b. Since the computational expense of each step is also typically of order h, the overall expense grows like h2.