2
$\begingroup$

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;

$\endgroup$
  • $\begingroup$ Are you interested in the cost of the Euclidian algorithm, or in the complexity of the problem? $\endgroup$ – Raphael Oct 14 '18 at 18:52
  • $\begingroup$ 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. $\endgroup$ – Raphael Oct 14 '18 at 18:54
  • $\begingroup$ What have you tried and where did you get stuck? $\endgroup$ – Raphael Oct 14 '18 at 18:54
  • $\begingroup$ 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. $\endgroup$ – zbh2047 Oct 15 '18 at 2:48
  • $\begingroup$ do you see the pattern $10^x$ gives $\approx 2 x$ $\endgroup$ – kelalaka Oct 15 '18 at 5:59
0
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ Yes, $O(\log n)$ is obvious, but I am curious about the lower bound. $\endgroup$ – zbh2047 Oct 15 '18 at 13:28
  • $\begingroup$ 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)$. $\endgroup$ – ydh28 Oct 15 '18 at 23:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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