Run time/Efficiency of finding Least Common Multiple

Question

The algorithm is: $$\mathrm{lcm}(x,y)=\frac{xy}{\gcd(x,y)}$$ And we can use the Euclidean algorithm for finding $\gcd$.

How is the complexity for above method $O(n^3)$, if $x,y$ can at maximum be $n$?

Answer 1

The solution stated [$O(n^3)$] is wrong. Euclid's algorithm for finding $\text{gdc}(p,q):p>q$ converges in at most $1+ \frac{\ln p}{\ln \phi}$ steps, where $\phi$ is the golden ratio $\frac{1+\sqrt{5}}{2}$.

You can see this as follows: Label the numbers encountered $p_k = p, p_{k-1} = q, p_{k-2} \ldots p_0 = 0$. Say, when you are at least one step from completion, the larger number is $p_n$ and the smaller is $p_{n-1}$. Then the step taken for $\text{gdc}(p_{n+1},p_n)$ was $$ p_{n+1} = k_n p_n + p_{n-1}$$ with $k_n \geq 1$; thus $$p_{n+1} \geq 1 \cdot p_n$$ Now what happened for $p_{n+2}$? $$ p_{n+2} = k_{n+1} p_{n+1} + p_n = (1 + k_{n+1}k_n) p_n + p_{n-1} \geq 2 p_n$$ And for $p_{n+3}$: $$ p_{n+3} = k_{n+2} p_{n+2} + p_{n+1} \geq 2\cdot p_n + 1 \cdot p_n = 3 p_n$$

Then $$p_{n+4} \geq (3+2)\cdot p_n$$ and so forth.

So the smallest possible number for $p$ in a $k$-step algorithm grows like the FIbonacci number $F_k$, which grows like $\phi^k$.

Since multiplication (or division) is itself an $O( \log n)$ operation, the algorithmic complexity of Euclid's algorithm is no greater than $$O((\log p)^2)$$ and if all multiplies and adds and divisions are counted as 1 operation, it is

$$ O(\log p)$$ where $p$ is the larger of the two numbers to start with.