Daca nu ma insel complexitatea algoritmului lui euclid este de O( log a * log b ) ? pentru a demonstra cred ca sa folosit teorema impartiri cu rest:
a:b = c, r;
a=b*c+r; r= a-b*c; r= a- b* [a/b]; r= a - b* ( a/b - {a/b} ) ; r= b*{a/b};
unde
- = parte intreaga de x si {y} parte fractionara din x