How to find upper-bound on the complexity to compute $\text{lcm}(a,b)$ using $\text{lcm}(a,b) = \frac{ab}{\gcd(a,b)}$

Question

I think the upper-bound complexity should be the sum of three parts:

1. the complexity of multiple $a$ and $b$
2. the complexity of $\gcd(a,b)$
3. the complexity of division

For (1), the complexity is $O(n^2)$

How to compute the complexity of gcd and the complexity of division?

Answer 1

Reference: https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations

Both GCD and division take $O(n^2)$ time, so overall complexity is $O(n^2)$.

Note that faster algorithms are mentioned in the reference, so it can be done even faster, just see the link for more information.