分析Euclid算法的时间复杂度的一个技巧是遵循两次迭代中发生的情况：

a', b' := a % b, b % (a % b)

现在，a和b都将减少，而不是仅减少一个，这使得分析更加容易。您可以将其分为几种情况：

• 小小A： 2a <= b
• 小小B： 2b <= a
• 小甲：2a > b但是a < b
• 小B：2b > a但是b < a
• 等于： a == b

现在，我们将显示每个案例都会使总数减少a+b至少四分之一：

• 微小的A：b % (a % b) < a和2a <= b，因此b减少了至少一半，因此a+b减少了至少25%
• 小B：a % b < b和2b <= a，因此a减少了至少一半，因此a+b减少了至少25%
• 小A：b将变为b-a，小于至少b/2减少。a+b``25%
• 小B：a将变得a-b小于a/2，a+b至少减少25%。
• 等于：a+b降至0，明显降低a+b了25%。

因此，通过案例分析，每一步a+b至少减少了25%。在a+b被迫降至之下之前，最多可以发生这种情况1。S直到达到0为止的总步数（）必须满足(4/3)^S <= A+B。现在就工作：

(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)

因此，迭代次数在输入位数方面是线性的。对于适合cpu寄存器的数字，将迭代建模为采用恒定时间并假装gcd 的 总 运行时间是线性的是合理的。

当然，如果要处理大整数，则必须考虑以下事实：每次迭代中的模运算没有固定成本。粗略地讲，总渐近运行时间将是多对数因子的n ^
2倍。有点像 n^2 lg(n) 2^O(log* n)。可以通过使用二进制gcd来避免多对数因子。