 Since the number of steps "N" grows linearly with "h", the running time is bounded by

Euclid's algorithm is widely used in practice, especially for small numbers, due to its simplicity.For comparison, the efficiency of alternatives to Euclid's algorithm may be determined.One inefficient approach to finding the GCD of two natural numbers "a" and "b" is to calculate all their common divisors; the GCD is then the largest common divisor.