One trick for analyzing the time complexity of Euclid’s algorithm is to follow what happens over two iterations:
a', b' := a % b, b % (a % b)
Now a and b will both decrease, instead of only one, which makes the analysis easier. You can divide it into cases:
- Tiny A:
2a <= b - Tiny B:
2b <= a - Small A:
2a > bbuta < b - Small B:
2b > abutb < a - Equal:
a == b
Now we’ll show that every single case decreases the total a+b by at least a quarter:
- Tiny A:
b % (a % b) < aand2a <= b, sobis decreased by at least half, soa+bdecreased by at least25% - Tiny B:
a % b < band2b <= a, soais decreased by at least half, soa+bdecreased by at least25% - Small A:
bwill becomeb-a, which is less thanb/2, decreasinga+bby at least25%. - Small B:
awill becomea-b, which is less thana/2, decreasinga+bby at least25%. - Equal:
a+bdrops to0, which is obviously decreasinga+bby at least25%.
Therefore, by case analysis, every double-step decreases a+b by at least 25%. There’s a maximum number of times this can happen before a+b is forced to drop below 1. The total number of steps (S) until we hit 0 must satisfy (4/3)^S <= A+B. Now just work it:
(4/3)^S <= A+B
S <= lg[4/3](A+B)
S is O(lg[4/3](A+B))
S is O(lg(A+B))
S is O(lg(A*B)) //because A*B asymptotically greater than A+B
S is O(lg(A)+lg(B))
//Input size N is lg(A) + lg(B)
S is O(N)
So the number of iterations is linear in the number of input digits. For numbers that fit into cpu registers, it’s reasonable to model the iterations as taking constant time and pretend that the total running time of the gcd is linear.
Of course, if you’re dealing with big integers, you must account for the fact that the modulus operations within each iteration don’t have a constant cost. Roughly speaking, the total asymptotic runtime is going to be n^2 times a polylogarithmic factor. Something like n^2 lg(n) 2^O(log* n). The polylogarithmic factor can be avoided by instead using a binary gcd.