The algorithm to be used is:

• Sort the set into assenting 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))$.

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

The algorithm to be used is:

• Sort the set into assenting order
• $x_1 = s_1$
• $x_i = gdc(x_{i-1},s_i)$
• $GDC = 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}$ and $gdc$ is $O(ln(n))$ so an upper bound should be $O(n\ln(n))$.

The algorithm to be used is:

• Sort the set into assenting 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))$.