On the Worst Case of CompIexity of Euclid's Algorithm

LI Xiaoming. On the Worst Case of CompIexity of Euclid's AlgorithmJ. Journal of Computer Research and Development, 1990, 27(2): 32-34.

Citation:

LI Xiaoming. On the Worst Case of CompIexity of Euclid's AlgorithmJ. Journal of Computer Research and Development, 1990, 27(2): 32-34.

Citation:

LI Xiaoming. On the Worst Case of CompIexity of Euclid's AlgorithmJ. Journal of Computer Research and Development, 1990, 27(2): 32-34.

Abstract

Taking a new approach, we have analysed the time complexity of Euchd's algorithm for computing the greatest common divisor of two positive integers The conctusion is: Let l(m, n) denote the numbet of iterations of execution of Euclid's algorithm upon input data m and n. Then l(m, n)<log; (m.n), provided that not both m and n are l's.

FullText(HTML)

Turn off MathJax

Article Contents

Export File