What is the maximum number of divisions made by Euclid’s algorithm among all inputs 1 ≤ m, n ≤ 10?
Answers
Answered by
5
Explanation:
5 divisions
The answer is 5 divisions, which is made by Euclid's algorithm in computing gcd(5,8). It is not too time consuming to get this answer by examining the number of divisions made by the algorithm on all input pairs 1 <m<n ≤ 10. Note: A pertinent general result (see [KnuII], p.
Similar questions