Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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. –  Guess who it is. Feb 15 '12 at 10:55
@Jyrki: You mean the binary GCD algorithm? –  Ilmari Karonen Feb 15 '12 at 12:26
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.