Recursive Calls in Euclidean Algorithm

Question

algorithm gcd(x,y)
     if y = 0 
        then return(x)
else return(gcd(y,x mod y))

we're given this as the euclidean algorithm.

I get everything up to "so in both cases the first argument decreases by..." But Im really confused about how we get the 2n.

Answer 1

If $x$ has $n$ bits, $\left\lfloor\frac{x}2\right\rfloor$ has $n-1$ bits, so decreasing $x$ by a factor of at least $2$ reduces the number of bits by at least $1$. After at most $n$ such reductions you reach $0$ bits, meaning that the first argument is $0$, and the algorithm terminates. It takes $2$ calls to ensure a reduction by a factor of at least $2$, so at worst it takes $2n$ calls to get $n$ reductions by a factor of at least $2$ and hence a $0$ first argument.

Answer 2

Let us look at the minimal numbers $a,b\in\mathbb{N}$, $a>b$ for which Euclid algorithm will have $n$ steps. It can be shown that $a\geq F_{n+2}$, and $b \geq F_{n+1}$, where $F$ defines Fibonacci sequence.

By induction on $n$.

Base: $n = 1$.

There are numbers $a=2$ and $b=1$.

Let the claim holds for $n-1$.

Let us look minimal numbers that are requires for $n$ steps.

There are numbers for which $a_1 = b$ and $b_1 = a\mod b$ require $n-1$ steps.

By the inductive assumption that numbers are $a_1 =F_{n+1}$ and $b_1=F_n$.

So, minimal numbers for $n$ steps are those which gives $b = F_{n+1}$ and $a = a_1 + b_1$. Therefore

$a = a_1 + b_1 = F_{n+1} + F_n = F_{n+2}.$

That concludes the proof.

Now, for the numbers $a, b\in\mathbb{N}$, $a>b$, $a\leq F_{n+2}$ we'll need not more than $n$ steps.