# The Average Running Time Of Euclid Algorithm?

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?

-
there is a nice pic of the runtime of the euclidean algorithm on wikipedia –  Peter Sheldrick Feb 15 '12 at 10:33
Knuth has a detailed analysis in The Art of Computer Programming. From what I recall, the average time is of the same order of the worst case; only the constants are different. See en.wikipedia.org/wiki/…. –  lhf Feb 15 '12 at 10:41
...and the worst case is when the inputs are two consecutive Fibonacci numbers. –  Ｊ. Ｍ. Feb 15 '12 at 10:55
For every d, there are infinitely many pairs (m,n) such that gcd(m,n)=d. How do you define the average? –  Tsuyoshi Ito Feb 15 '12 at 12:59
What do you mean by “define it in the limit”? –  Tsuyoshi Ito Feb 19 '12 at 18:59