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

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?

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)$$.
You need to show that $$n^2$$ is not $$o(n log^k n)$$ for any k.
• 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$? – Lawerance Oct 27 '18 at 11:41
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 25, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8986051082611084, "perplexity": 187.51066852538497}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2019-35/segments/1566027322160.92/warc/CC-MAIN-20190825000550-20190825022550-00091.warc.gz"}