Question

Give an efficient algorithm to compute the least common multiple of two n-bit numbers $\mathbf{x}$ and $\mathbf{y}$, that is, the smallest number divisible by both$\mathbf{x}$ and $\mathbf{y}$. What is the running time of your algorithm as a function of $\mathbf{n}$?

Short answer

The final time complexity can be written as $\mathrm{O}\left({\mathrm{n}}^3\right)$.

Step-by-step solution

Introduction

The least common multiple can be defined as the smallest factor of the two numbers and the running time complexity can be defined as the total amount of time taken to complete the process. It generally analyzes the time taken at each step and finally, it computes the final time complexity.

Algorithm to compute LCM(x,y)

Consider,$\mathrm{LCM}(\mathrm{x},\mathrm{y})$

Store common multiple of $\mathrm{x}$and$\mathrm{y}$ in any variable $\mathrm{z}$.

Check whether the variable$\mathrm{z}$ is divisible by$x$ and$\mathrm{y}$ , that is, use the algorithm:

While ()

$\mathrm{If}(\mathrm{z}\mathrm{\%}\mathrm{x}==0\&\mathrm{z}\mathrm{\%}\mathrm{y}==0)$

$\mathrm{Return}\mathrm{z}$

$\mathrm{Else}$

$\mathrm{z}++$

$\mathrm{LCM}(\mathrm{x},\mathrm{y})$ can be written as$(\mathrm{x}\times \mathrm{y})÷\gcd (\mathrm{x},\mathrm{y})$ .

Time complexity of the algorithm

For$\mathrm{x}*\mathrm{y}$ the time complexity of that part is$\mathrm{O}\left({\mathrm{n}}^2\right)$ and to find GCD we need time complexity equal to $\mathrm{O}\left({\mathrm{n}}^3\right)$. So, final time complexity can be written as $\mathrm{O}\left({\mathrm{n}}^3\right)$.