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.

• Raphael: Note that "complexity" is the wrong word here. Problems have complexities, algorithms have runtimes.

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.

• elmazzun: Thank you again, I wish my Professor could explain like you.
• babou: In the input size, what is the initial 2 for?
• David Richerby: @babou It takes 1ドル+\lfloor \log_2 x\rfloor$ bits to write $x$ in binary but I didn't bother to write the floor.