7
$\begingroup$

What is the average running time of Euclid Algorithm with respect to all possible input pairs $(m,n)$ such that $\gcd(m,n) = d$?

It seems very hard to deduce from the recurrence $T(m,n) = T(n, m \bmod n)+1$.

Any better ideas?

  • 5
    Knuth has a detailed analysis in *The Art of Computer Programming*. From what I recall, the average time is of the same order of the worst case; only the constants are different. See http://en.wikipedia.org/wiki/Euclidean_algorithm#Average_number_of_steps.2012-02-15
  • 4
    ...and the worst case is when the inputs are two consecutive Fibonacci numbers.2012-02-15
  • 0
    I was sickened to the bone, when a friend showed me that an algorithm depending on (here $m,n$ are both **odd**) the recurrence relations (IIRC): $$gcd(2m,2n)=2gcd(m,n),$$ $$gcd(2m,n)=gcd(m,2n)=gcd(m,n)=gcd(min\{n,m\},|m-n|/2),$$ depending on the parity of the inputs has a better worst case complexity than Euclid, because here the size of the new input is alway at most one half of the previous, whereas in Euclid's Algorithm the size may only go down by a factor of the Golden Ratio (see the comment by J.M.)2012-02-15
  • 2
    @Jyrki: You mean the [binary GCD algorithm](http://en.wikipedia.org/wiki/Binary_GCD_algorithm)?2012-02-15
  • 4
    For every d, there are infinitely many pairs (m,n) such that gcd(m,n)=d. How do you define the average?2012-02-15
  • 0
    @Ilmari, that's the one. Thanks for the link (and the name of the algorithm).2012-02-15
  • 0
    @TsuyoshiIto, maybe to define it in the limit.2012-02-19
  • 2
    What do you mean by “define it in the limit”?2012-02-19
  • 1
    @J.M. The numbers need not be Fibonacci numbers; you can seed the recurrence $a_n = a_{n - 1} + a_{n - 2}$ with any initial values and consecutive pairs of this sequence will perform just as badly.2012-02-29

1 Answers 1