It was difficult for me to calculate the time complexity of the binary GCD algorithm, also known as the Stein algorithm, which is given as O (n ^ 2), where n is the number of bits in the larger two numbers. Shouldn't it be O (n)? The algorithm is as follows:
1.gcd (0, v) = v, because everything divides zero, and v is the largest number dividing v. Similarly, gcd (u, 0) = u. gcd (0, 0) is usually not defined, but it is convenient to set gcd (0, 0) = 0.
2. If u and v are both even, then gcd (u, v) = 2 · gcd (u / 2, v / 2), since 2 is a common divisor.
3. If u is even and v is odd, then gcd (u, v) = gcd (u / 2, v), since 2 is not a common divisor. Similarly, if both is odd and v is even, then gcd (u, v) = gcd (u, v / 2).
4. If u and v are both odd and u ≥ v, then gcd (u, v) = gcd ((u - v) / 2, v). If both are odd and u <v, then gcd (u, v) = gcd ((v - u) / 2, u). These are combinations of one step of a simple Euclidean algorithm that uses subtraction at each step and application of the above step 3. Division by 2 leads to an integer, since the difference of two odd numbers is even. [3]
5. Repeat steps 2-4 to u = v or (one more step) to u = 0. In any case, the GCD is 2kv, where k is the number of common coefficients 2 found in step 2.