What is the Complexity of Euclid’s Algorithm?

Subscribe to my newsletter to hear about my latest posts. No spam, I promise.

---

Euclid’s algorithm is one of the earliest algorithms ever recorded. It finds the Greatest Common Divisor or “GCD” between two integers $a$ and $b$ with $a>b$. As an example, the GCD of $36$ and $27$ is $9$ as it is the largest integer that divides both numbers.

One simple way to find this GCD is to iterate over all integers between $1$ and $b$ (the lowest of the two) and find the largest one dividing both $a$ and $b$. This brute force approach is of complexity $O(b)$.

Euclid’s algorithm elegantly leverages the fact that the GCD of two numbers is also the GCD of their difference to significantly reduce computation time.

Starting from our intuition, this must be better than the brute force method $O(b)$, but how much exactly?

Let $a_0=a$ and $b_0=b$.
In the following update, $a_1=b_0$ and $b_1=a_0\mathrm{mod}{b}_0$.
More generally, $a_{k+1}=b_k$ and $b_{k+1}=a_k\mathrm{mod}{b}_k$.

Using the properties of the modulo operator, it can be proven that $b_{k+2}\le \frac{b_k}{2}$. In English, that b will more at least be divided by 2 after two steps of Euclid’s algorithm.

Quickly validating this with a quick example, with $a_0=72$ and $b_0=54$:

$a_1=54,b_1=72\mathrm{mod}54=18$
$a_2=18,b_2=54\mathrm{mod}18=0$

The proof is beyond the scope of this article (see Appendix for a proof), but this finding can be empirically validated by computing $b_0$ and $b_2$ for all combinations of $a$ and $b$ within the range $[1,500]$ and plotting their ratio.

Computer Simulation

Distribution of the ratio of $b_2$ to $b_0$

Python code used to generate the chart

import matplotlib.pyplot as plt

def euclid_algorithm(a, b):
    b0 = b
    a1 = b
    b1 = a % b
    if b1 == 0:
        return b0, None
    a2 = b1
    b2 = a1 % b1
    
    return b0, b2

ratios = []

for a in range(1, 501):
    for b in range(1, 501):
        if a > b:
            b0, b2 = euclid_algorithm(a, b)
            if b2 is not None:
                ratio = b2 / b0
                ratios.append(ratio)

plt.hist(ratios, bins=50, edgecolor='black')
plt.xlabel('Ratio (b2 / b0)')
plt.ylabel('Frequency')
plt.title('Distribution of the Ratio between b0 and b2')
plt.show()

Achieving Logarithmic Upper-Bound

Given the fact the upper-bound $b_{k+2}\le \frac{b_k}{2}$, we can show that the time complexity of Euclid’s algorithm is $O(log(n))$.

Using our Computer Science intuition, the division by 2 points to a logarithmic decrease.

As $b$ is divided by 2 every two steps, we need to find the number of steps needed ($k$) to get $b\le 1$.

Putting this into mathematical form, we get:

$\frac{b_0}{2^{k/2}}=1$
$2^{k/2}=b_0$
$\frac{k}{2}=\log (b_0)$
$k=2\log (b_0)⟹O(\log (b))$

Final Thoughts

In its beautiful simplicity, Euclid’s algorithm is a prime example of leveraging information about a problem to avoid exhaustive search. By exploiting the fact that two numbers’ Greatest Common Divisor is also the Greatest Common Divisor of their difference, this algorithm recursively reduces the problem - reaching a time complexity of $O(\log (b))$.

Related Articles

Smart Algorithms Use Meta-Information to Solve a Problem

Appendix

Proving $b_{k+2}\le \frac{b_k}{2}$

Before going into further details, let’s remember how Euclid’s algorithm works with the example of $a_0=72$ and $b_0=54$.

We can summarise the steps in the following table:

Step Number	$a$	$b$
0	72	54
1	54	18
2	18	0

The update rule of Euclid’s algorithm is as follows:

$$\{\begin{array}{l}{a}_{k+1}=b_k\\ b_{k+1}=a_k\mathrm{mod}{b}_k\end{array}$$

Now, how to prove that $b_{k+2}$ is always less than ${\displaystyle \frac{b_k}{2}}$? There are two cases to study:

Case 1: $b_{k+1}<{\displaystyle \frac{b_k}{2}}$

In this case, $b_{k+1}$ is already less than ${\displaystyle \frac{b_k}{2}}$. This is the case at the first update of the example above, with $b_0=54$ and $b_1=18$.

Case 2: $b_{k+1}>{\displaystyle \frac{b_k}{2}}$

We observe the following:

$$\begin{array}{}\text{(1)}& b_{k+1}=a_k\mathrm{mod}{b}_k\end{array}$$

$$\begin{array}{}\text{(2)}& b_{k+2}=b_k\mathrm{mod}{b}_{k+1}\end{array}$$

If $b_{k+1}>{\displaystyle \frac{b_k}{2}}$, then:

$$\begin{array}{}\text{(3)}& b_k\mathrm{mod}{b}_{k+1}=b_k-b_{k+1}\end{array}$$

This is due to the division rule of the quotient and remainder:

$$b_k=b_{k+1}\times 1+(b_k-b_{k+1})$$

So, the remainder is $b_k-b_{k+1}$.

Substituting equation $(3)$ into equation $(2)$, we get:

$$\begin{array}{}\text{(4)}& b_{k+2}=b_k-b_{k+1}\end{array}$$

From $b_{k+1}>{\displaystyle \frac{b_k}{2}}$, we have:

$$b_k-b_{k+1}<b_k-{\displaystyle \frac{b_k}{2}}={\displaystyle \frac{b_k}{2}}$$

Substituting back into equation $(4)$, we obtain:

$$\begin{array}{}\text{(5)}& b_{k+2}<{\displaystyle \frac{b_k}{2}}\end{array}$$

Thus, in both cases, we have shown that $b_{k+2}<{\displaystyle \frac{b_k}{2}}$.