Compare Asymptotic Complexities

Arrange the below functions in the increasing order of their asymptotic complexity:

A(n) = 2ⁿ
B(n) = n^3/2
C(n) = n * lg(n)
D(n) = n^lg(n)

Solution:

In order to evaluate an algorithm independently of the input, the notion of time complexity is introduced. The time complexity T(n) is a function of the problem size n. The value of T(n) is the running time of the algorithm in the worst case, i.e. the number of steps it requires at most with an arbitrary input.

We may talk in terms of upper bounds/lower bounds or Best case / Worst Case Avg case time complexities.

This question is not about defining or understanding asymptotic notations and asymptotic complexities. Will take them in some other article later.

The question is about arranging the above function in the increasing order.

As a thumb rule:
 - Exponential functions (constant raised-to-the-power n) are usually the most time consuming.
 - If, the exponent function is variable-raised to the power variable than it is even more time consuming
   (provided the powers are same, if powers are not same then higher power is more time consuming).

So function A and D are more complex. And among them A is more complex than D (compare powers).

D < A

Amongst B & C B is more time consuming.

C < B

Hence:

C < B < D < A