Question

Suppose that you have two different algorithms for solving a problem of size n. The first algorithm uses exactly n(log n) operations and the second algorithm uses exactly n 3/2 operations. As n grows, determine which algorithm uses fewer operations?

Answer 1

Answer:

Algorithm 1 uses:

n*log(n) operations.

While algorithm 2 uses:

n^(3/2) operations.

We want to see, as n grows, which algorithm uses fewer operations.

So we would want to first solve:

n*log(n) = n^(3/2)

This will give us the exact value of n such that the number of operations is the same in both algorithms.

dividing both sides by n we get:

log(n) = n^(3/2)/n = n^(3/2 - 1) = n^(1/2)

where we can use:

log(n) = ln(n)/ln(10)

ln(n) = ln(10)*n^(1/2)

This equation actually has no solutions.

This happens because the right side is always larger than the left side.

Then, the same thing happens for our two initial equations:

n^(3/2) is always larger than n*log(n), as you can see in the graph below, where n^(3/2)  is represented with the orange graph:

So we can conclude that the fist algorithm uses less operations as n grows.