Number of iterations of the Euclidean algorithm

Question

I have a doubt about the runtime of the Euclidean algorithm; the slide of my Professor says:

The calculation of $\mathrm{GCD} (a, b)$ stops at the most after $2\log_2 a$ iterations.

1. Since $\log_2 a$ is the size of the input,
2. calculation requires a linear number of iterations.
3. The algorithm therefore has polynomial runtime.

I don't get how he could deduce (2) from (1), and (3) from (2); until now, the only concept of theory that he gave us is that to represent a positive integer, we need $1+\log_2 x$ bits.

Answer 1

There's very little to deduce.

The number of iterations is linear in the size of the input because the size of the input is $2+\log_2 a + \log_2 b$ and the number of iterations is $2\log_2 a$, which is less than $2(2+\log_2 a + \log_2 b)$, so is less than twice the length of the input. Hence, (2) holds.

Each iteration requires only a polynomial number of steps: all it does is tests and simple arithmetic operations, all of which can be done in time polynomial in the number of bits involved. Therefore, the total required time is some linear function (the number of iterations) times some polynomial function (the cost of each iteration), which is another polynomial function. So (3) holds.