(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 
.
. This is due to:
respectively. Once one of them becomes 0 the algorithm terminates, so the algorithm terminates in at most 
, which implies 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)
