Question

Put the following complexity classes in ascending order.

O(n log n)

O(n)

O(2^n)

O(n^3)

Answer 1

Solution:

Explanation:

=>Let say f1(n) = O(nlogn), f2(n) = O(n), f3(n) = O(2^n) and f4(n) = O(n^3)

Finding asymptotic growth rate:

=>We know the growth rate of functions: exponential function > polynomial function > logarithmic function > constant function > decreasing function

=>f1(n) = O(nlogn) and is combination of polynomial and logarithmic functions.

=>f2(n) = O(n) and is polynomial function.

=>f3(n) = O(2^n) and is exponential function.

=>f4(n) = O(n^3) and is polynomial function.

Finding order:

=>f3(n) > f4(n) > f1(n) > f2(n)

I have explained each and every part with the help of statements attached to the answer above.