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
1  
there is a nice pic of the runtime of the euclidean algorithm on wikipedia –  Peter Sheldrick Feb 15 '12 at 10:33
5  
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
4  
...and the worst case is when the inputs are two consecutive Fibonacci numbers. –  J. M. Feb 15 '12 at 10:55
4  
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
2  
What do you mean by “define it in the limit”? –  Tsuyoshi Ito Feb 19 '12 at 18:59

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.