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
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 19, 2010 at 13:01 | comment | added | Gerry Myerson | @BCS, how much better can the upper bound be? Suppose the numbers are $F_{k-1},F_k,1+F_k,\dots,n-2+F_k$. Then the sum, $T$, is roughly $nF_k$, and the gcd of $F_{k-1}$ and $F_k$ takes $O(\log F_k)$, which is $O\log(T/n)$. And putting the numbers in order in the first place is $O(n\log n)$. So it would seem that this case achieves the upper bound, no? | |
| May 18, 2010 at 23:02 | comment | added | Gerry Myerson | @Dror, the quote is from the answer to which these comments are attached. $T$ is the sum of the elements. If there are $n$ elements, and they're all ones and twos, their sum is within a constant multiple of $n$. Indeed, it's between $n$ and $2n$. | |
| May 18, 2010 at 16:13 | comment | added | BCS |
I think Gerry's right that Bradley's paper can show an upper bound of $O(\ln(T/n) + n\ln(n))$ but I rather suspect that the upper bound is in fact much lower. (BTW, I love this line from page 435: "The assumption that nature is non-malicious leads one to expect fewer iterations than the bound would suggest."
|
|
| May 18, 2010 at 16:01 | comment | added | Dror Speiser | @Gerry: is the quote from a previous version of the question? I guess I got here after an edit. But still, sorting ones and twos is linear. | |
| May 18, 2010 at 15:55 | comment | added | BCS | will someone please add a link to the article cited in this answer? cacm.acm.org/magazines/1970/7/… | |
| May 18, 2010 at 12:54 | comment | added | Gerry Myerson | "...if the elements are all ones and twos...$T$ is within a constant multiple of $n$". I hope BCS has a look at the Bradley paper, I think it has everything BCS needs. | |
| May 18, 2010 at 12:00 | comment | added | Dror Speiser | The example of ones and twos is a bit off since ordering them takes $O(n)$ and not $O(n\log n)$ (bucket sort). Also, why is $T$ within a constant multiple of $n$? | |
| May 18, 2010 at 3:26 | history | edited | Gerry Myerson | CC BY-SA 2.5 |
added information in view of comment received
|
| May 18, 2010 at 1:03 | comment | added | BCS |
Assuming that I'm only using unique positive integers (as far as I know GDC is only defined for them and non unique value can be ignored) then you can approximate it as $2n < \sqrt(T)$ so the sort is cheep ($O(\sqrt(n)\ln(n))$) and, I think, uninteresting to the big-o of finding $GCD(S)$.
|
|
| May 18, 2010 at 0:54 | history | answered | Gerry Myerson | CC BY-SA 2.5 |