 Its computational complexity is
The computational complexity is usually given in terms of the length of the input.Here, this length is formula_15 and the complexity is thus

If "a" and "b" are both nonzero, the greatest common divisor of "a" and "b" can be computed by using least common multiple (lcm) of "a" and "b"