Question

JAVA: Which of the following growth-rate functions would correspond to the shortest running time?

		cubic
		exponential
		quadratic
		N log N

Answer 1

Which of the following growth-rate functions would correspond to the shortest running time?

Growth rate of functions determines the running time of the function. Running time of the function is dependent on the size of inputs , n.

1. cubic - O(n³)

2. exponential - O(2ⁿ )

3. quadratic - O(n² )

4 N log N - O(n log(n))

The cubic growth rate and quadratic growth rate are similar but cubic growth rate increases faster than quadratic growth rate (since the growth rate is multiplied with an extra n in cubic)

The N log (N) growth rate has lesser running time than quadratic because value of log(n) is less than n for all n. Hence N log(N) will be faster than O(N²)

In exponential growth rate an extra unit of n doubles the growth rate of the function. Hence with larger values of n the growth rate will be very large. It has the highest running time.

So the order of the growth rate in ascending order is :

N log N < N² < N³ < 2^N i.e

N log N < quadratic < cubic < Exponential

The shortest running time corresponds to N log N.