# Time complexity of Euclidean algorithm

Consider Euclidean algorithm to find $$GCD(a,b)$$ as follow:

$$\gcd(a, b) = \begin{cases}a,&\text{if }b = 0 \\ \gcd(b, a \bmod b),&\text{otherwise.}\end{cases}.$$

I read this link, suppose $$a\geq b$$, I think the running time of this algorithm is $$O(\log_ba)$$. My argument is as follow that consider two cases:

1. $$b\leq \frac{a}{b}$$, then $$a\mod b\leq \frac{a}{b}$$, because
let $$a\mod b=x$$ so $$0\leq x.

2. $$b>\frac{a}{b}$$, then $$a\mod b\leq \frac{a}{b}$$, because
let $$a\mod b=x$$ so $$x$$ is at most $$\frac{a}{b}$$ because at each step when we compute $$a\mod b$$, we decrease at least $$a$$ by a factor of $$\frac{a}{b}$$ so $$a\mod b\leq \frac{a}{b}$$.

Consequently, computing $$GCD(a,b)$$ has running time $$O(\log_ba)$$. Above argument is true or not?

• Your formula is wrong. The complexity is not $O(\log_b a)$, but $O(\log\min a,b)$. No argument cannot prove a wrong formula.
– user16034
Apr 26, 2022 at 16:49
• Why my formula is wrong? Could you explain more? Apr 26, 2022 at 17:08
• I gave the correct formula.
– user16034
Apr 26, 2022 at 18:32

I'm not convinced your proof of the first case above is correct. Also, initially, the upper bound for $$a \mod b$$ is $$a/b$$, but $$b$$ will be replaced by a smaller value before the next iteration. So, the upper bound doesn't seem to reduce by the same constant factor $$b$$ in each iteration.
Your final answer that the complexity of Euclid's algorithm is $$O(\log a)$$ is correct. Here's a proof:
Suppose the Euclidean algorithm Euclid(a,b) is used to compute gcd(a,b), where $$a > b$$. We show that $$a \mod b < a/2$$. Consider two cases: (i) Suppose $$b \le a/2$$. Then, the remainder $$a \mod b < b \le a/2$$, and we're done. (ii) Suppose $$b > a/2$$. Then, $$a-b < a/2$$, whence $$a \mod b < a/2$$.
After one iteration, the pair $$(a,b)$$ is replaced by $$(b, a \mod b)$$, and after another iteration by $$(a \mod b, c)$$ for some $$c$$. Thus, after two iterations, $$a$$ is replaced by a number $$< a/2$$. In general, after every two iterations, the first number in the pair is reduced by a factor of at least $$2$$. Hence, the total number of iteration is $$O(\log a)$$.
• Your last comment might leave the impression that $\log_b a$ and $\log a$ are equivalent in the asymptotic sense. This is not true.