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 to the power (3/2) operations. As n grows, which algorithm uses fewer operations?

Answer 1

Answer:

First algorithm will have fewer comparison than second as the value of n grows.

Step-by-step explanation:

As n grows, first algorithm will perform better then other.

Consider the ratio of number of comparison done by second algorithm with number of comparison done by first algorithm, the ratio will be $n^{3 / 2} /(n \log (n))=\sqrt{n} / \log n=\log 2^{\sqrt{n}} / \log n$

Since log function is monotonically increasing function and $2^{\sqrt{n}}>n$ for all $n>4$. Hence first algorithm will have fewer comparison than second as the value of n grows.