Qual é a complexidade temporal do algoritmo GCD de Euclides?

Considerar quaisquer dois passos do algoritmo.

Em algum momento, você tem os números [matemática](a,b)[/math] com [matemática]a > b[/math]. Após o primeiro passo, estes passam para [matemática](b,c)[/math] com [matemática]c=a\bmod b[/math], e após o segundo passo os dois números serão [matemática](c,d)[/math] com [matemática]d=b\bmod c[/math].

P>Agora pense ao contrário. Como [matemática]d=b\bmod c[/math], sabemos que [matemática]b=kc+d[/math] para alguns [matemática]k > 0[/math]. A menor possibilidade é [matemática]k=1[/math], portanto [matemática]b\geq 1c+d = c+d[/math].

Daquele resultado e de [matemática]a > b[/math] obtemos [matemática]a > c+d[/math]. Se adicionarmos as duas últimas desigualdades que acabámos de derivar, obtemos que [matemática](a+b) > 2(c+d)[/math].
Em palavras, após cada dois passos consecutivos a soma dos dois números diminui para menos de metade do seu tamanho original.

Agora olhemos para o primeiro passo do algoritmo. No início, temos alguns [matemática](a,b)[/math] com [matemática]a > b[/math]. Após o primeiro passo temos [matemática](b,c)[/math] com [matemática]c=a\bmod b[/math], e claramente [matemática]b > c[/math]. Assim, após o primeiro passo, ambos os números são no máximo iguais ao menor dos dois números de entrada.

P>Pomos esses dois resultados juntos, podemos concluir que o número de iterações (chamadas recursivas em outras implementações) é no máximo logarítmico no menor número de entrada. Em outras palavras, o número de iterações é no máximo linear no número de dígitos no número de entrada menor.

Para ver que esta análise é assimptticamente ótima, tome [matemática](a,b)=(F_{n+1},F_n)[/math] -- ou seja, dois números de Fibonacci consecutivos.