Search code examples
mathexponential

Sorting the order of growth of the functions?

Please order the function belows by growth rate from fastest to slowest:

  • n^10
  • 2^n
  • nlog(n)
  • 10^6

And my answer is:

  • 2^n
  • n^10
  • nlog(n)
  • 10^6

Is my answer correct?

Solution

  • That seems about right. As way of education, consider what happens when you feed in different n values (using rough powers of 10 rather than exact values):

     n      2^n       n^10    n log n   10^6
 ----   -------   -----   -------   ----
    1   10^0.3    10^0    10^0      10^6
   10   10^3      10^10   10^1      10^6
  100   10^30     10^20   10^2      10^6
 1000   10^301    10^30   10^3      10^6
10000   10^3010   10^40   10^4      10^6

    So, in terms of how fast they grow, you're list is correct.

    • 106 doesn't grow at all.
    • n log n increases its power-of-ten by one for each step.
    • n10 increases its power-of-ten by 10 for each step.
    • 2n multiplies its power-of-ten by ten each step.