Editing Euclidean algorithm (section)

==== Worst-case ====

If the Euclidean algorithm requires ''N'' steps for a pair of natural numbers ''a''&nbsp;>&nbsp;''b''&nbsp;>&nbsp;0, the smallest values of ''a'' and ''b'' for which this is true are the [[Fibonacci number]]s ''F''<sub>''N''+2</sub> and ''F''<sub>''N''+1</sub>, respectively.<ref name="Knuth, p. 343">{{harvnb|Knuth|1997}}, p. 343</ref> More precisely, if the Euclidean algorithm requires ''N'' steps for the pair ''a''&nbsp;>&nbsp;''b'', then one has ''a''&nbsp;≥&nbsp;''F''<sub>''N''+2</sub> and ''b''&nbsp;≥&nbsp;''F''<sub>''N''+1</sub>. This can be shown by [[mathematical induction|induction]].<ref>{{Harvnb|Mollin|2008|p=21}}</ref> If ''N''&nbsp;=&nbsp;1, ''b'' divides ''a'' with no remainder; the smallest natural numbers for which this is true is ''b''&nbsp;=&nbsp;1 and ''a''&nbsp;=&nbsp;2, which are ''F''<sub>2</sub> and ''F''<sub>3</sub>, respectively. Now assume that the result holds for all values of ''N'' up to ''M''&nbsp;−&nbsp;1. The first step of the ''M''-step algorithm is ''a''&nbsp;=&nbsp;''q''<sub>0</sub>''b''&nbsp;+&nbsp;''r''<sub>0</sub>, and the Euclidean algorithm requires ''M''&nbsp;−&nbsp;1 steps for the pair ''b''&nbsp;>&nbsp;''r''<sub>0</sub>. By induction hypothesis, one has ''b''&nbsp;≥&nbsp;''F''<sub>''M''+1</sub> and ''r''<sub>0</sub>&nbsp;≥&nbsp;''F''<sub>''M''</sub>. Therefore, ''a''&nbsp;=&nbsp;''q''<sub>0</sub>''b''&nbsp;+&nbsp;''r''<sub>0</sub>&nbsp;≥&nbsp;''b''&nbsp;+&nbsp;''r''<sub>0</sub>&nbsp;≥&nbsp;''F''<sub>''M''+1</sub>&nbsp;+&nbsp;''F''<sub>''M''</sub>&nbsp;=&nbsp;''F''<sub>''M''+2</sub>,
which is the desired inequality.
This proof, published by [[Gabriel Lamé]] in 1844, represents the beginning of [[computational complexity theory]],<ref>{{Harvnb|LeVeque|1996|p=35}}</ref> and also the first practical application of the Fibonacci numbers.<ref name="Knuth, p. 343"/>

This result suffices to show that the number of steps in Euclid's algorithm can never be more than five times the number of its digits (base 10).<ref>{{Harvnb|Mollin|2008|pp=21–22}}</ref> For if the algorithm requires ''N'' steps, then ''b'' is greater than or equal to ''F''<sub>''N''+1</sub> which in turn is greater than or equal to ''φ''<sup>''N''−1</sup>, where ''φ'' is the [[golden ratio]]. Since ''b''&nbsp;≥&nbsp;''φ''<sup>''N''−1</sup>, then ''N''&nbsp;−&nbsp;1&nbsp;≤&nbsp;log<sub>''φ''</sub>''b''. Since log<sub>10</sub>''φ''&nbsp;>&nbsp;1/5, (''N''&nbsp;−&nbsp;1)/5&nbsp;<&nbsp;log<sub>10</sub>''φ''&nbsp;log<sub>''φ''</sub>''b''&nbsp;=&nbsp;log<sub>10</sub>''b''. Thus, ''N''&nbsp;≤&nbsp;5&nbsp;log<sub>10</sub>''b''. Thus, the Euclidean algorithm always needs less than [[Big O notation|''O''(''h'')]] divisions, where ''h'' is the number of digits in the smaller number ''b''.