I was trying to figure out the running time of the euclidean algorithm. The analysis that I found on Wikipedia and CLRS both analyze the run time of the euclidean algorithm using the Fibonacci recurrence (which I feel is rather unintuitive, so I was looking for something different). However, I remember reading a different analysis and that one can argue that it does at most $2n$ operations where $n = O(\log{b})$ (i.e. the number of bits). I remember that the argument went something like this: "In the worst case, Euclid's algorithm takes two steps to divide one of its inputs in half." However, I was having problems re-producing this argument.
So far this is what I have.
let $a_t$ and $b_t$ be the input to our gcd(a,b) program at iteration t (i.e. $\gcd(a_t,b_t)$. I have that after two iteration we have done:
$\gcd(a_t, \ b_t)$
$\gcd(a_{t+1}, \ b_{t+1}) = \gcd(b_t, \ a_t \pmod {b_t}) = \gcd(b_t, a_t – q b_t)$
$\gcd(a_{t+2}, \ b_{t+2}) = \gcd(a_t \pmod {b_t} , \ b_t \pmod {(a_t – q b_t)})$
And if one thinks in terms of bits, if $b_t$ is a power of 2, say $b_t = 2^k$, then after two steps the mod clear at least k bits from the n bit of $a_t$ to the k+1th bit of $a_t$. So for $a_{t+2}$ a bunch of higher order bits have been cleared. If we compare doing that to bit-shifting only by one bit to the right (i.e. dividing by 2), that only clears at most 1 bit, which means that after two operations, gcd at least halfs $a_t$. Which means that it clears a bit every two operations, so the run time should take worst-case 2n (if only manages to clear 1 bit every 2 iterations). However, this argument only works is $b_t$ is a power of 2 and it doesn't feel "rigorous" enough or solid enough, anyone know what I am missing?
Thanks in advance!
Best Answer
Here's one way of looking at it: WLOG, assume that $a_0\gt b_0$; then one step of the algorithm takes $(a_0, b_0)\mapsto (a_1, b_1) = (b_0, a_0\bmod b_0)$. Now, we can break into two cases: either $b_0\leq \frac{a_0}2$ or $b_0\gt \frac{a_0}2$.
If $b_0\leq\frac{a_0}2$, then we have by definition $a_1\leq \frac{a_0}2$, and since $b_1\leq a_1$ then $b_1\leq\frac{a_0}2$.
On the other hand, if $b_0\gt\frac{a_0}2$, we have $b_1 = a_0\bmod b_0 = a_0-b_0$ since $b_0\lt a_0 \lt 2b_0$; and because $b_0\gt \frac{a_0}2$, $b_1=a_0-b_0\lt\frac{a_0}2$.
In either case, since $a_2=b_1$ then we have that $a_2\leq\frac{a_0}2$; therefore the larger input must be divided at least by two every two steps. This is enough to show that the algorithm takes $O(\log n)$ steps to find the GCD of two numbers $\leq n$, though of course this analysis is too coarse to give the correct leading constant.