Timeline for Time complexity of finding the GCD of a set S as a function of sum(S)
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 20, 2010 at 9:07 | comment | added | AVS | A correct upper bound on the complexity of computing the gcd of two integers of length k is $O(k log^2 k log log k)$, or more generally, $O(M(k) log k)$, where $M(k)$ is the cost of multiplication. This bound is achieved by the algorithm of Knuth and Schonhage, and also by the algorithm of Stehle and Zimmermann, see perso.ens-lyon.fr/damien.stehle/downloads/recbinary.pdf. | |
| May 18, 2010 at 15:05 | history | edited | Grigory Yaroslavtsev | CC BY-SA 2.5 |
deleted 202 characters in body
|
| May 18, 2010 at 12:03 | comment | added | Dror Speiser | It might be desirable to edit the claim on gcd complexity to either soft-oh notation, or to add the actual logarithmic factors that make the claim true. Except that, the answer is complete, probably can't do better than $nk$. | |
| May 18, 2010 at 0:16 | history | undeleted | Grigory Yaroslavtsev | ||
| May 17, 2010 at 23:56 | history | deleted | Grigory Yaroslavtsev | ||
| May 17, 2010 at 23:39 | comment | added | Grigory Yaroslavtsev | Well, the big-O notation gives us an upper bound on the complexity, so the bounds I gave hold, but probably can be further improved. | |
| May 17, 2010 at 23:24 | comment | added | BCS |
I don't think that last bit holds. finding gdc takes $O(min(k_1,k_2))$ and and for the special case where the next value is a multiple of the gcd so far it take $O(1)$ so all the values being equal is a fast case. As for all the values being nearly equal, the $x_i$ value will very quickly become small and again result in a fast case. OTOH what I'm interested in is the worst case and the average case.
|
|
| May 17, 2010 at 23:16 | comment | added | BCS |
Oops, that $ln(n)^2$ should have been $ln(n)$
|
|
| May 17, 2010 at 22:32 | history | answered | Grigory Yaroslavtsev | CC BY-SA 2.5 |