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?