# Number of iterations of the Euclidean algorithm

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.

• Note that "complexity" is the wrong word here. Problems have complexities, algorithms have runtimes.
– Raphael
May 19 '14 at 7:27

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.
• @babou It takes $1+\lfloor \log_2 x\rfloor$ bits to write $x$ in binary but I didn't bother to write the floor. Apr 24 '14 at 16:13