Question

Suppose that you have two different algorithms for solving a problem. To solve a problem of size n, the first algorithm uses exactly \(n(\log n)\)operations and the second algorithm uses exactly \({n^{\frac{3}{2}}}\) operations. As \(n\) grows, which algorithm uses fewer operations?

Short answer

As \(n\) grows, \(n(\log n)\) will use fewer operations.

Step-by-step solution

Step 1:

Now, considering \(f(x) = n(\log n)\) and

\(g(x) = {n^{\frac{3}{2}}}\).

\(\begin{array}{l}f(x) = n(\log n)\\ \Rightarrow f(x) \le n.n\\ \Rightarrow f(x) \le {n^2}\end{array}\)

\( \Rightarrow f(x) \le {n^{\frac{3}{2}}}\)…… When \(n\)is sufficiently large.

\( \Rightarrow f(x) \le g(x)\)

Thus, if we compare \(f(x) \le g(x)\) with the definition of Big-\(O\) Notation, that is \(|f(x)| \le C|g(x)|,\) we can imply that \(n(\log n)\)is \(O({n^{\frac{3}{2}}})\).

Step 2:

As, \(n(\log n)\)is \(O({n^{\frac{3}{2}}})\), we can conclude that \(n(\log n)\) will use lesser operations than \({n^{\frac{3}{2}}}\), as \(n\) grows.

Hence, as \(n\) grows, \(n(\log n)\) will use fewer operations.