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

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
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$
3
  • $\begingroup$ Yes, $O(\log n)$ is obvious, but I am curious about the lower bound. $\endgroup$
    – zbh2047
    Oct 15, 2018 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, 2018 at 23:07
  • $\begingroup$ @zbh2047: you didn't ask a lower bound, did you ? And from a given $O$ bound, you can't derive a lower bound. $\endgroup$
    – user16034
    Apr 28, 2022 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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