Search code examples
performancetime-complexityruntime-compilation

Time complexity in ascending order

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.

Solution

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

      enter image description here

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

    • Since

      enter image description here

      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:

      enter image description here

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

    • Using a logarithm law transformation we obtain the following:

      enter image description here

      Thus (6) < (3).

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

    (1). enter image description here

    (5). enter image description here

    (4). enter image description here

    (6). enter image description here

    (3). enter image description here

    (2). enter image description here

    (7). enter image description here

    (8). enter image description here