3
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ Thank you again, I wish my Professor could explain like you. $\endgroup$ – elmazzun Apr 24 '14 at 10:15
  • $\begingroup$ In the input size, what is the initial 2 for? $\endgroup$ – babou Apr 24 '14 at 16:09
  • $\begingroup$ @babou It takes $1+\lfloor \log_2 x\rfloor$ bits to write $x$ in binary but I didn't bother to write the floor. $\endgroup$ – David Richerby Apr 24 '14 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.