Time complexity of Euclidean algorithm

Question

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<b$.

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?

• user16034: 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.
• ErroR: Why my formula is wrong? Could you explain more?
• user16034: I gave the correct formula.

Answer 1

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)$.

• user16034: Your last comment might leave the impression that $\log_b a$ and $\log a$ are equivalent in the asymptotic sense. This is not true.
• Ashwin Ganesan: @YvesDaoust thanks for pointing this out. Have edited it out.