Qual è la complessità temporale dell'algoritmo GCD di Euclide?

Considera due passi qualsiasi dell'algoritmo.

A un certo punto, hai i numeri [math](a,b)[/math] con [math]a > b[/math]. Dopo il primo passo questi diventano [math](b,c)[/math] con [math]c=a\bmod b[/math], e dopo il secondo passo i due numeri saranno [math](c,d)[/math] con [math]d=b\bmod c[/math]. Poiché [math]d=b\bmod c[/math], sappiamo che [math]b=kc+d[/math] per qualche [math]k > 0[/math]. La possibilità più piccola è [math]k=1[/math], quindi [math]b\geq 1c+d = c+d[/math].

Da questo risultato e da [math]a > b[/math] si ottiene [math]a > c+d[/math]. Se aggiungiamo le ultime due disuguaglianze appena derivate, otteniamo che [math](a+b) > 2(c+d)[/math].
In parole povere, dopo ogni due passi consecutivi la somma dei due numeri diminuisce a meno della metà della sua dimensione originale.

Ora guardate il primissimo passo dell'algoritmo. All'inizio abbiamo dei [math](a,b)[/math] con [math]a > b[/math]. Dopo il primissimo passo abbiamo [math](b,c)[/math] con [math]c=a\bmod b[/math], e chiaramente [math]b > c[/math]. Quindi, dopo il primo passo entrambi i numeri sono al massimo uguali al più piccolo dei due numeri in ingresso.

Mettendo insieme questi due risultati, possiamo concludere che il numero di iterazioni (chiamate ricorsive in altre implementazioni) è al massimo logaritmico nel più piccolo numero in ingresso. In altre parole, il numero di iterazioni è al massimo lineare nel numero di cifre del numero più piccolo in ingresso.

Per vedere che questa analisi è asintoticamente ottimale, prendiamo [math](a,b)=(F_{n+1},F_n)[/math] -- cioè due numeri di Fibonacci consecutivi.