0
$\begingroup$

The algorithm to be used is:

  • Sort the set into ascending order
  • $x_1 = s_1$
  • $x_i = gcd(x_{i-1},s_i)$
  • $GCD = x_n$

What I'm looking for is expected run time as a function of $\sum_{i\in S}i$

As a starting point $|S| \leq \sum_{i\in S} i$ and gcd is $O(ln(n))$ so an upper bound should be $O(n\ln(n))$.

Improve this question
$\endgroup$
8
  • $\begingroup$ I don't understand your algorithm. Suppose the set S is 6, 10, 15. Then $x_1=6$, $x_2=2$, $x_3=1$. How exactly do you propose to combine these numbers to get the LCM, which is 30? $\endgroup$
    – Gerry Myerson
    Commented May 17, 2010 at 23:43
  • $\begingroup$ Oops. I should have re-read the Wikipedia article, step 4 only works for 2 inputs. $\endgroup$
    – BCS
    Commented May 17, 2010 at 23:49
  • $\begingroup$ I guess the whole thing doesn't work. OTOH the part I'm curious about is step 1-3 so, I'l fix the question to just ask about that. $\endgroup$
    – BCS
    Commented May 17, 2010 at 23:52
  • $\begingroup$ You can modify it like this: keep the set of numbers $S$ and then $n - 1$ times extract two minimal elements from the set, calculate their $lcm$ and then put it back into the set. $\endgroup$
    – Grigory Yaroslavtsev
    Commented May 17, 2010 at 23:55
  • 1
    $\begingroup$ While I am in favor of numbers giving their approval, I think you want them to be in ascending rather than assenting order. $\endgroup$
    – Joel David Hamkins
    Commented May 19, 2010 at 17:14

2 Answers 2

Reset to default
1
$\begingroup$

Sorting a set of $n$ elements into ascending order takes $O(n\log n)$. You ask for a bound in terms of the sum, call it $T$, of the elements, rather than their number. I suspect that if the elements are all ones and twos and they are sufficiently jumbled up then there is no way to significantly improve on the time required to order them, and of course $T$ is within a constant multiple of $n$, so you still get $O(T\log T)$.

Edit: Exercise 36 in 4.5.3 of Knuth, Seminumerical Algorithms, may be relevant. The question asks, what is the smallest value of $u_n$ such that the calculation of $\gcd(u_1,\dots,u_n)$ [by the method of this question] requires $N$ divisions? The answer given is $u_n=F_{N-n+3}$, where $F_m$ is (I'm pretty sure) the $m$-th Fibonacci number. There's a reference to a paper of G H Bradley, CACM 13 (1970) 433-436, 447-448.

Improve this answer
$\endgroup$
8
  • $\begingroup$ 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)$. $\endgroup$
    – BCS
    Commented May 18, 2010 at 1:03
  • $\begingroup$ 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$? $\endgroup$
    – Dror Speiser
    Commented May 18, 2010 at 12:00
  • $\begingroup$ "...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. $\endgroup$
    – Gerry Myerson
    Commented May 18, 2010 at 12:54
  • $\begingroup$ will someone please add a link to the article cited in this answer? cacm.acm.org/magazines/1970/7/… $\endgroup$
    – BCS
    Commented May 18, 2010 at 15:55
  • $\begingroup$ @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. $\endgroup$
    – Dror Speiser
    Commented May 18, 2010 at 16:01
1
$\begingroup$

Finding greatest common divisor ($gcd$) of two numbers of length $k$ takes $O(k)$ time. Suppose that all the numbers have equal length $k$, then complexity will be $O(nk)$, which is $O(n \log(\frac{S}{n}))$. This is in fact the case of maximum complexity for a fixed $n$ and $S$. Because in general case the time complexity be something like $O(\sum_i \log x_i)$ and from convexity of the $\log$ function it follows that maximum is achieved when all $\log x_i$ are equal.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Oops, that $ln(n)^2$ should have been $ln(n)$ $\endgroup$
    – BCS
    Commented May 17, 2010 at 23:16
  • $\begingroup$ 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. $\endgroup$
    – BCS
    Commented May 17, 2010 at 23:24
  • $\begingroup$ 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. $\endgroup$
    – Grigory Yaroslavtsev
    Commented May 17, 2010 at 23:39
  • $\begingroup$ 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$. $\endgroup$
    – Dror Speiser
    Commented May 18, 2010 at 12:03
  • 2
    $\begingroup$ 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. $\endgroup$
    – AVS
    Commented May 20, 2010 at 9:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .