Running time analysis on computing the largest factor of an integer using Euler's subtraction-based algorithm

Question

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?

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.

• Lawerance: 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$?
• gnasher729: 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.