# 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? – Raphael Oct 14 '18 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. – Raphael Oct 14 '18 at 18:54
• What have you tried and where did you get stuck? – Raphael Oct 14 '18 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. – zbh2047 Oct 15 '18 at 2:48
• do you see the pattern $10^x$ gives $\approx 2 x$ – kelalaka Oct 15 '18 at 5:59

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. – zbh2047 Oct 15 '18 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)$. – ydh28 Oct 15 '18 at 23:07