For any b at or below a, the remainder a % b is always below a / 2. If b is at most a / 2 then the remainder is smaller than b and so smaller than a / 2. If b is larger than a / 2 then the quotient is 1 and the remainder is a - b, again below a / 2. One step turns (a, b) into (b, a % b), so it takes two steps for that halved value to reach the front of the pair, and the leading number is below half of what it was every two steps. That is what gives O(log n). The slowest possible input is a pair of neighbouring Fibonacci numbers, where every quotient comes out as 1, so each step is a single subtraction and nothing more.