What is the average running time of Euclid Algorithm with respect to all possible input pairs $(m,n)$ such that $\gcd(m,n) = d$?
It seems very hard to deduce from the recurrence $T(m,n) = T(n, m \bmod n)+1$.
Any better ideas?
What is the average running time of Euclid Algorithm with respect to all possible input pairs $(m,n)$ such that $\gcd(m,n) = d$?
It seems very hard to deduce from the recurrence $T(m,n) = T(n, m \bmod n)+1$.
Any better ideas?
The number of steps needed to compute $\gcd(m,n)$ is given by the length of the continued fraction of $\frac{m}{n}$, hence the worst case is to compute the $\gcd$ of two consecutive Fibonacci numbers (since $\frac{F_{n+1}}{F_n}=[1;1,\ldots,1]$) and an upper bound for the number of steps involved is: $ 1+\frac{\log(\max(m,n))}{\log\varphi} $ where $\varphi$ is the golden ratio $\varphi=\frac{1+\sqrt{5}}{2}$.