Sort the following complexities:
- Think of what happens when is extremely large.
- If in doubt, try to break the term into multiple multiplication steps.
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.