How bad could it be?

Let's try to learn something about the worst-case running-time of the Euclidean GCD algorithm. If you actually run through the example on some inputs, you'll see that the remainders keep getting smaller and smaller until we hit zero and, in practice, they seem to gert small fast. So a bad case for the Euclidean algorithm is when they get small slowly, and it takes lots of steps to get to zero. So, the key is this: what gives us big remainders? Well, in dividing $a$ by $b$, if $b$ is too close to $a$, the quotient is 1 and there is only a small amount of leftover, which is the remainder, $r$. On the other hand, if $b$ is small, then $r$ is necessarily small, since it must be less than $b$. So, as with Bears, the middle is "just right". If $b = \lfloor a/2 \rfloor + 1$ we get the largest possible remainder. Even so, we have the following: \[ r \lt 1/2 a \] If we apply this to the Euclidean algorithm, we get the following (where $r_i$ is the remainder at the $i$th step: \[ \begin{array}{cccl} a&b&r&\text{bound}\\ \hline a&b&r_1&\lt a/2\\ b&r_1&r_2&\lt b/2\\ r_1&r_2&r_3&\lt a/2^2\\ r_2&r_3&r_4&\lt b/2^2\\ \vdots&\vdots&\vdots&\vdots\\ r_{2k-2}&r_{2k-1}&r_{2k}&\lt b/2^k\\ \end{array} \] So, after $2 \lg b$ steps we have $r_{2\lg b} \lt 1$ which means the algorithm is done. This gives an upper bound of $2 \lg b$ on the number of steps (i.e. recursive calls). Note, however, that this is not the same as the running time. Why? Because each step requires a "mod" operation, and when the integers involved are too big to fit in a machine word, these mods will no longer take constant time!

So, we make $O(\lg b)$ loop iterations. The actual worst-case running time depends on how quickly we can do division and find remainders, since we do one such computation per iteration. The "grade-school" method for division of $a$ by $b$ is $O((\log a)^2)$. There are better ways to do division, but we don't have time. In any event, this gives us a worst case running time $T_w(a,b) \in O(\lg b (\lg a)^2)$

A lower bound on how bad it could be

The Unit Notes have a nice derivation of a $\Omega(\lg b)$ lower bound on the number of steps in the Euclidean algorithm. It comes from the observation that consecutive Fibanocci numbers are worst-case input for the Eucliean algorithm. Why the Fibanocci numbers? Well, if $F_{k+1}$ and $F_k$ are consecutive Fibanocci numbers, the Euclidean algorithm for GCD($F_{k+1}$,$F_k$) actually traces back the sequence of Fibanocci numbers in the remainders it computes. Thus, we get the interesting fact that the Eculidean algorithm for GCD($F_{k+1}$,$F_k$) takes $k$ steps. How can we use this? Well, some clever mathematicians have shown that: \[ F_k = \lfloor \frac{\phi^k}{\sqrt{5}} + \frac{1}{2} \rfloor \text{, where } \phi = \frac{1 + \sqrt{5}}{2} \] So, if $b = F_k = \lfloor \frac{\phi^k}{\sqrt{5}} + \frac{1}{2} \rfloor$ then $b \leq \frac{\phi^k}{\sqrt{5}} + \frac{1}{2}$. Take log of both sides we get \[ \begin{array}{rcl} \lg (b-1/2) &\leq& k \lg \phi - \lg{\sqrt{5}}\\ \lg (b/2) &\leq& k \lg \phi - \lg{\sqrt{5}}\\ \lg b - 1 &\leq& k \lg \phi - \lg{\sqrt{5}}\\ \lg b + \lg{\sqrt{5}} - 1&\leq& k \lg \phi\\ \frac{1}{\lg \phi}\lg b + \frac{\lg{\sqrt{5}} - 1}{\lg \phi}&\leq& k \end{array} \] where $\phi$ is a constant. So we end up with $k \in \Omega(\lg b)$. Putting that together with the bound from the previous section, we see that the worst-case number of while-loop iterations of Euclid's GCD algorithm is $\Theta(\lg b)$.