Tight time complexity for GCD

Revision en1, by Noam527, 2018-12-11 23:21:21

(prologue) Some time ago this crossed my mind, but I only recalled it now and I think it could be worth a small blog post. This is nothing big and rarely useful but nevertheless, I found it interesting so hopefully you will too.

It is widely known that the time complexity to compute the GCD (greatest common divisor) of two integers a, b, using the euclidean algorithm, is .

Short proof

This bound is nice and all, but we can provide a slightly tighter bound to the algorithm:

We show this bound by adding another sentence to the above proof: once the smaller element becomes 0, we know that the larger element becomes the resulting gcd. Therefor we can first bound by , and lastly notice that we can change the maximum to minimum, since after one step of the algorithm the current maximum is the previous minimum; $\min(a, b)

Tags gcd

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English Noam527 2018-12-12 00:22:53 0 (published)
en4 English Noam527 2018-12-12 00:22:15 946
en3 English Noam527 2018-12-11 23:58:39 835 Tiny change: ' \log(G_i)$' -> ' \log(G_i) = \log(G_0) - \log(G_{n-1}) < \log(G_0) \leq \log M$.'
en2 English Noam527 2018-12-11 23:40:12 1221 Tiny change: '\min(a, b)' -> '\min(a, b) = \max(b, a \, % \, b)$ when $a \geq b$.'
en1 English Noam527 2018-12-11 23:21:21 1653 Initial revision (saved to drafts)