Time complexity in ascending order

Question

What is the ascending order of growth rate of the following functions:

1. 2^((logn)^1/2)

2. 2^n

3. 2^(n/2)
4. n^(4/3)
5. n(logn)^3
6. n^logn
7. 2^(n^2)

8. n!

   log n is with base 2.

Answer 1

• We can immediate deduce that n! is the highest order, as it is equal to

  

  ... and the n^n part far exceeds any of the other functions.

• Since

  

  We can deduce that (1) is less than other functions with n as the base, e.g. (4), (5) and (6). In fact it is less than all of the other functions.

• (3) < (2), since the latter is the former squared.

• (2) < (7), since the latter is the former to the power n.

• (4) < (6), since log n > 4/3.

• From this post, log n grows more slowly than any positive power of n. Therefore:

  

  Thus (5) < (4), (6)

• Using a logarithm law transformation we obtain the following:

  

  Thus (6) < (3).

---

Compiling all of the reasoning steps above, we deduce the ascending order to be:

(1).

(5).

(4).

(6).

(3).

(2).

(7).

(8).