Editing Euclidean algorithm (section)

=== Computational expense per step ===
In each step ''k'' of the Euclidean algorithm, the quotient ''q''<sub>''k''</sub> and remainder ''r''<sub>''k''</sub> are computed for a given pair of integers ''r''<sub>''k''−2</sub> and ''r''<sub>''k''−1</sub>
: {{math|1=''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>.}}

The computational expense per step is associated chiefly with finding ''q''<sub>''k''</sub>, since the remainder ''r''<sub>''k''</sub> can be calculated quickly from ''r''<sub>''k''−2</sub>, ''r''<sub>''k''−1</sub>, and ''q''<sub>''k''</sub>
: {{math|1=''r''<sub>''k''</sub> = ''r''<sub>''k''−2</sub> − ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub>.}}

The computational expense of dividing ''h''-bit numbers scales as {{math|''O''(''h''(''ℓ'' + 1))}}, where {{mvar|ℓ}} is the length of the quotient.<ref name="Knuth-257-261">{{harvnb|Knuth|1997}}, pp. 257–261</ref>

For comparison, Euclid's original subtraction-based algorithm can be much slower. A single integer division is equivalent to the quotient ''q'' number of subtractions. If the ratio of ''a'' and ''b'' is very large, the quotient is large and many subtractions will be required. On the other hand, it has been shown that the quotients are very likely to be small integers. The probability of a given quotient ''q'' is approximately {{math|ln {{abs|''u''/(''u'' − 1)}}}} where {{math|1=''u'' = (''q'' + 1)<sup>2</sup>}}.<ref>{{harvnb|Knuth|1997}}, p. 352</ref> For illustration, the probability of a quotient of 1, 2, 3, or 4 is roughly 41.5%, 17.0%, 9.3%, and 5.9%, respectively. Since the operation of subtraction is faster than division, particularly for large numbers,<ref>{{cite book | last = Wagon | first = S. | author-link = Stan Wagon | year = 1999 | title = Mathematica in Action | publisher = Springer-Verlag | location = New York | isbn = 0-387-98252-3 | pages = 335–336}}</ref> the subtraction-based Euclid's algorithm is competitive with the division-based version.<ref>{{Harvnb|Cohen|1993|p=14}}</ref> This is exploited in the [[binary GCD algorithm|binary version]] of Euclid's algorithm.<ref>{{Harvnb|Cohen|1993|pp=14–15, 17–18}}</ref>

Combining the estimated number of steps with the estimated computational expense per step shows that the Euclid's algorithm grows quadratically (''h''<sup>2</sup>) with the average number of digits ''h'' in the initial two numbers ''a'' and ''b''. Let {{math|''h''<sub>0</sub>, ''h''<sub>1</sub>, ..., ''h''<sub>''N''−1</sub>}} represent the number of digits in the successive remainders {{math|''r''<sub>0</sub>, ''r''<sub>1</sub>, ..., ''r''<sub>''N''−1</sub>}}. Since the number of steps ''N'' grows linearly with ''h'', the running time is bounded by
<!-- : <math alt="The order of the sum over all i less than N of h sub i times parenthesis h sub i minus h sub i plus one plus 2 close parenthesis is a subset of the order of h times the sum over all i less than N of h sub i minus h sub i plus one plus 2, which in turn is a subset of the order of h times h sub zero plus 2 N, which in turn is a subset of the order of h squared."> -->
: <math>
O\Big(\sum_{i<N}h_i(h_i-h_{i+1}+2)\Big)\subseteq O\Big(h\sum_{i<N}(h_i-h_{i+1}+2) \Big) \subseteq O(h(h_0+2N))\subseteq O(h^2).</math>