For the following algorithm,

$X\leftarrow \{(i, n - i) | i = 1, ..., n- 1\}$

while $\max_{(a, b)\in X}b > 0$ do

$\quad X \leftarrow \{(|a - b|, \min\{a, b\})|(a, b) \in X\}$

return $\max_{(a, b)\in X}a$

show that the algorithm does not run in $o(n \log ^k n)$ for any constant $k$.

Summary: the algorithm uses the Euler's subtraction-based algorithm to compute the largest factor of $n$ in $1$ to $n - 1$.

My work: I can prove the upper bound case that $T(n) \in O(n^2)$. Since $n = (a + b)$ is strictly decreasing, gcd computation for each tuple takes at most $n$ operations. Since there are $n-1$ elements, $T(n) \in O(n^2)$.

I can also prove the lower bound case that $T(n) \in \Omega(n \log n)$. The best case for computing gcd of a single tuple occurs if $a = c_1 \cdot b$ or $b = c_2 \cdot a$ for $c_1, c_2 \in \mathbb{N}$. Then, the running time is $\Omega{\log n}$. Therefore, the total running time is $T(n) \in \Omega(n \log n)$.

My problem: But I don't know how to proceed from here. Basically, I need to prove $T(n) \in \Omega{(n^{1+\epsilon})}$ for $\epsilon > 0$. This means I need to prove something polynomial with the gcd computation of a single tuple.

Can anyone help me out with this problem?


1 Answer 1


It seems the algorithm tries to calculate n-1 gcd's simultaneously, and performs n-1 operations as long as one of the gcd's is not found. And since at least one gcd (gcd (n, 1)) takes n iterations, it is $\Theta (n^2)$.

Of course that is just due to the stupid implementation, but probably a good example for estimating the runtime of an algorithm, not the runtime of a problem.

You need to show that $n^2$ is not $o(n log^k n)$ for any k.

  • $\begingroup$ Can you explain why $T(n) \in \Omega(n^2)$? It's true at least one gcd takes n iterations. But there are other gcds that take log time. How do you know that when you sum them up, the total runtime is on the order of $n^2$? $\endgroup$
    – Lawerance
    Oct 27, 2018 at 11:41
  • $\begingroup$ Read the first line in my answer carefully. The algorithm doesn't do what you think it does. The amount of work it does is n^2. The amount of useful work it does is much much less. $\endgroup$
    – gnasher729
    Oct 27, 2018 at 13:47

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.