How to prove that extended euclidean algorithm has time complexity $log(max(m,n))$?

Question

I tried to search on internet and also thought by myself but was unsuccessful. Intuitively i think it should be O(max(m,n)). can someone give easy explanation since i am beginner in algorithms.

Answer 1

Hints:

In the Euclidean algorithm, the decay of the variables is obtained by the division of the largest by the smallest, using $a=bq+r$ i.e. $r=a-bq$, then swapping $a,b\to b,r$, as long as $q>0$. It is clear that the worst case occurs when the quotient $q$ is the smallest possible, which is $1$, on every iteration, so that the iterations are in fact

$$a,b\to b,a-b.$$

If you reverse this assignment, you get

$$a,b\to a+b,b$$

and you obtain the recurrence relation that defines the Fibonacci sequence.

Hence the longest decay is achieved when the initial numbers are two successive Fibonacci, let $F_n,F_{n-1}$, and the complexity is $O(n)$ as it takes $n$ step to reach $F_1=F_0=1$.

Now we know that $F_n=O(\phi^n)$ so that $$\log(F_n)=O(n).$$