Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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))$.

share|improve this question
    
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? –  Gerry Myerson May 17 '10 at 23:43
    
Oops. I should have re-read the Wikipedia article, step 4 only works for 2 inputs. –  BCS May 17 '10 at 23:49
    
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. –  BCS May 17 '10 at 23:52
    
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. –  Grigory Yaroslavtsev May 17 '10 at 23:55
1  
While I am in favor of numbers giving their approval, I think you want them to be in ascending rather than assenting order. –  Joel David Hamkins May 19 '10 at 17:14
show 3 more comments

2 Answers

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.

share|improve this answer
    
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)$. –  BCS May 18 '10 at 1:03
    
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$? –  Dror Speiser May 18 '10 at 12:00
    
"...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. –  Gerry Myerson May 18 '10 at 12:54
    
will someone please add a link to the article cited in this answer? cacm.acm.org/magazines/1970/7/… –  BCS May 18 '10 at 15:55
    
@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. –  Dror Speiser May 18 '10 at 16:01
show 3 more comments

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.

share|improve this answer
    
Oops, that $ln(n)^2$ should have been $ln(n)$ –  BCS May 17 '10 at 23:16
    
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. –  BCS May 17 '10 at 23:24
    
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. –  Grigory Yaroslavtsev May 17 '10 at 23:39
    
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$. –  Dror Speiser May 18 '10 at 12:03
1  
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. –  AVS May 20 '10 at 9:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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