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.
- Since $\log_2 a$ is the size of the input,
- calculation requires a linear number of iterations.
- 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.