# Time Complexity of Euclidean Algorithm

In this article, we will discuss the time complexity of the Euclidean Algorithm which is * O(log(min(a, b))* and it is achieved.

**Euclid’s Algorithm****:** It is an efficient method for finding the GCD(Greatest Common Divisor) of two integers. The time complexity of this algorithm is * O(log(min(a, b))*. Recursively it can be expressed as:

gcd(a, b) = gcd(b, a%b),

where, a and b are twointegers.

**Proof:** Suppose, a and b are two integers such that **a >b** then according to Euclid’s Algorithm:

gcd(a, b) = gcd(b, a%b)

Use the above formula repetitively until reach a step where **b** is **0**. At this step, the result will be the **GCD of the two integers**, which will be equal to **a**. So, after observing carefully, it can be said that the time complexity of this algorithm would be proportional to the number of steps required to reduce **b** to **0**.

Let’s assume, the number of steps required to reduce **b** to **0** using this algorithm is **N**.

gcd(a, b) ------> N steps

Now, if the Euclidean Algorithm for two numbers **a** and **b** reduces in **N** steps then, **a** should be at least **f _{(N + 2)}** and

**b**should be at least

**f**.

_{(N + 1)}gcd(a, b) ——> N steps

Then, a >= f_{(N + 2)}and b >= f_{(N + 1)}

where, f_{N}is the N^{th}term in the Fibonacci series(0, 1, 1, 2, 3, …) and N >= 0.

To prove the above statement by using the **Principle of Mathematical Induction(PMI)**:

**Base Case:**- Let’s assume
**a = 2**and**b = 1**. Then,**gcd(2, 1)**will reduce to**gcd(1, 0)**in**1**step, i.e.,**N = 1**. - This means
**2**should be**at least f**and_{3}**1**should be**at least f**and_{2}**f**and_{3}= 2**f**._{2}= 1 - This implies,
**a**is at least**f**and_{(N + 2)}**b**is at least**f**._{(N + 1)} - It can be concluded that the statement holds true for the Base Case.

- Let’s assume
**Inductive Step:**Assume that the statement holds true for the**(N – 1)**. So, Below are the steps to prove it for the^{th}Step**N**:^{th}Step

gcd(b, a%b) ——> (N – 1) steps

Then,

b >= f_{(N – 1 + 2)}i.e., b >= f_{(N + 1)}

a%b >= f_{(N – 1 + 1)}i.e., a%b >= f_{N}

- It can also be written as:

a = floor(a/b)*b + a%b

floor(a/b)*b means highest multiple which is closest to b.

ex – floor(5/2)*2 = 4. If we then add 5%2=1, we will get a(=5) back.

- Now, (a/b) would always be greater than 1 ( as a >= b). So, from the above result, it is concluded that:

a >= b + (a%b)

This implies, a >= f_{(N + 1)}+ f_{N}

- It is known that each number is the sum of the two preceding terms in a Fibonacci series. This implies
**f**_{(N + 2)}= f_{(N + 1)}+ f_{N}.

a >= f

_{(N + 2)}and b >= f_{(N + 1)}

- Since the above statement holds true for the inductive step as well. This proves that the statement is correct.
- Before proceeding further, Look at the
**Binet Formula**:

**Binet Formula:**

f

_{N}= {((1 + √5)/2)^{N}– ((1 – √5)/2)^{N}}/√5

or

f_{N}≈ ∅^{N}

- where,
**∅**is known as the golden**ratio(∅≈1.618)**, and f_{N}is the N^{th}Fibonacci Number. - Now, it is already stated that the time complexity will be proportional to N i.e., the number of steps required to reduce
**b**to**0**. - So, to prove the time complexity, it is known that:

f

_{N}≈ ∅^{N}

N ≈ log_{∅}(f_{N})

Now, from the above statement, it is proved that using the Principle of Mathematical Induction, it can be said that if the Euclidean algorithm for two numbers **a** and **b** reduces in **N steps** then, **a** should be at least **f _{(N + 2) }**and

**b**should be at least

**f**.

_{(N + 1)}From the above two results, it can be concluded that:

=> f

_{N+1}≈ min(a, b)

=> N+1 ≈ log_{∅}min(a, b)=> O(N) = O(N+1) = log(min(a, b))