无标题文章

# Sort Complexities

## Aug. 17, 2016

Question

Sort the following complexities:

e^ne​n​​

n!n!

n^{100}n​100​​

n^nn​n​​

Hint

Think of what happens whennnis extremely large.

If in doubt, try to break the term into multiple multiplication steps.

Solution

It is pretty clear thatn^{100} < n^nn​100​​ 100n>100. It is also clear thate^n < n^ne​n​​ en>e.

What is fuzzy for many is where shouldn!n!fit in. Let us break the complexities down into smaller terms:

en=e×e×e×…×e×en!=n×n−1×n−2×…×2×1nn=n×n×n×…×n×nen=e×e×e×…×e×en!=n×n−1×n−2×…×2×1nn=n×n×n×…×n×n

As you can see above, asnngrows,n!n!easily overtakese^ne​n​​. Therefore, the answer is\enspace n^{100} < e^n < n! < n^nn​100​​

Below is a useful Big-O Complexity Graph for you to visualize how the number of operations grow asnnincreases.