For the following algorithm,

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

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

$\quad X \leftarrow \{(|a - b|, \min\{a, b\})\mid(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?


Your Answer

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

Browse other questions tagged or ask your own question.