0
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 26 at 16:49
  • $\begingroup$ Why my formula is wrong? Could you explain more? $\endgroup$
    – ErroR
    Apr 26 at 17:08
  • $\begingroup$ I gave the correct formula. $\endgroup$ Apr 26 at 18:32

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Your last comment might leave the impression that $\log_b a$ and $\log a$ are equivalent in the asymptotic sense. This is not true. $\endgroup$ Apr 26 at 16:51
  • $\begingroup$ @YvesDaoust thanks for pointing this out. Have edited it out. $\endgroup$ Apr 26 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.