# How to estimate the average time complexity of greatest common divisor?

As we know, the time complexity of $$\gcd(x,y)$$ is $$O(\log \min(x,y))$$ by using Euclidean algorithm. Now we fix a constant $$n$$ and consider the average time complexity of $$\gcd(x,n)$$.

Formally, let $$f(x)$$ be the number of divisions when calculating $$\gcd(x,n)$$. How to give a bound of $$\frac 1 n \sum_{x=1}^n f(x)$$?

I don't konw whether it is strictly $$o(\log n)$$ or $$\Theta(\log n)$$. How to prove the bound?

I list some of $$n$$ and the coresponding value here.

$$n$$ ; $$\frac 1 n \sum_{x=1}^n f(x)$$
1000;6.42;
10000;8.34;
100000;10.26;
1000000;12.20;
10000000;14.13;
100000000;16.07;

• Are you interested in the cost of the Euclidian algorithm, or in the complexity of the problem? Oct 14, 2018 at 18:52
• Note that the averaging sum you give is not what we commonly call "average case". The latter averages about all inputs of the same size (typically $n$) while your sum averages over all numbers up to value (!) $n$, i.e. including all smaller inputs as well. Oct 14, 2018 at 18:54
• What have you tried and where did you get stuck? Oct 14, 2018 at 18:54
• Yes, I just want to fix a variable and sum over the other. I have written a program to check the value, as listed above. Oct 15, 2018 at 2:48
• do you see the pattern $10^x$ gives $\approx 2 x$ Oct 15, 2018 at 5:59

If you start wit a pair (a, b), a>=b, one step goes to (b,a’) with a’ < a/2. This gives an easy upper bound for the number is steps. You can analyse two steps from (a, b) to (a’, b,’) and get a slightly better upper bound.

For a lower bound for the highest number of steps, if a and b are the n-th an (n-1)-st Fibonacci number, then you will go through pairs of Fibonacci numbers and take n steps.

Since $$n\geq x$$ in your sum, $$O(\log\min(x,n))$$ simplifies to $$O(\log x)$$. Being very careless with constants here, but $$\frac{1}{n}\sum\limits_{x=1}^n f(x)=\frac{1}{n}\left(n\cdot O(\log n)\right)=O(\log n)$$

I'm not sure what this is calculating though; average runtime of all input sizes less than $$n$$?

• Yes, $O(\log n)$ is obvious, but I am curious about the lower bound. Oct 15, 2018 at 13:28
• Looking at your calculations, it seems that the values do correspond to about $2\log n$. So without a thorough analysis (just looking at the calculations), I would say it is $\Theta(\log n)$. Oct 15, 2018 at 23:07
• @zbh2047: you didn't ask a lower bound, did you ? And from a given $O$ bound, you can't derive a lower bound.
– user16034
Apr 28, 2022 at 13:44