Question

Sort the following complexities:


Hint

  1. Think of what happens when is extremely large.
  2. If in doubt, try to break the term into multiple multiplication steps.

Solution

It is pretty clear that , as long as . It is also clear that as is a constant, which holds true as long as .

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

As you can see above, as grows, easily overtakes . Therefore, the answer is .

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

Big-O Complexity Graph