Run time/Efficiency of finding Least Common Multiple 
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$?
 A: 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.
