Efficiency Analysis of the Euclidean GCD algorithm

Question

The question is, if the Euclidean algorithm is called with values $p$, and $q$ such that $p < q$. Then runtime of the Euclidean algorithm is upper bounded by $O(\log_{3/2}(p+q))$. How can this be proved?

It means that the variables, will decrease by factor of $3/2$ on every step. So let's say the Euclidean algorithm has variables $m$ and $n$.
In step 1: m = p, n = q
Step 2: m = p mod q and n = p
and so on
So if we prove that, (m+n in step 1)/(m+n in step 2) >= 3/2 then we can solve the question.

I tried something like:
step 1: m = p, n = q
step 2: m = p', n= q'
q' = p and
p' = p mod q which is definitely <= p
this means q'+ p' <= 2p
But this is not taking me anywhere. Can someone help me with this.

Answer 1

Say we apply one step of the algorithm to the pair $(p, q)$ with $p\leq q$, and we get the pair $(q', p)$ as a result, with $q'<p$. We now split into cases:

• If $p \geq \frac q2$, then $$\begin{align}q'+p&{}\leq(q-p)+p\\ &=q\\ &=\frac23\left(q+\frac12q\right)\\ &\leq \frac23(q+p)\end{align}$$
• If $p\leq \frac q2$, then $$\begin{align}q'+p\leq{}& 2p\\={} &\frac23\cdot3p\\={}&\frac23(2p+p)\\\leq{}&\frac23(q+p)\end{align}$$