Computer science - time complexity examples

Sorting functions by time complexity

Question : Sort the following functions by time complexity

Step by step guide

The first thing that we need to do to sort those functions is categorizing them. Also as is the number of inputs, . is assumed to be We can see that this expression break into 2 parts : and . By intuition, we can tell that
  • the first expression is more complex than the second one .
  • We then take the more complex expression and categorize it. The multiplier can be removed as it does not affect the time complexity type, in this case.
In the second expression, the complexity decreases as increases. So we assume that the complexity is constant. This expression is an example of exponentiation. In this case, the base is equal to the power. The above expression is the of . We can see that the of is less complex than as the complexity will never exceed 1. . The complexity is constant as it does not increase with increasing input. The complexity is calculated with the biggest power. Multipliers can be ignored as they do not affect so much the complexity compared to the exponent. . denotes the factorial on A tricky one ! . The complexity is exponential. We can split this expression into 2 parts : and . As is more complex in time that , we take as complexity.

Categorizing the complexities

We now see that there are some groups of time complexities in our question :
  • Constant
  • Powers, exponents and factorial

Constant time complexity

Log time complexity

Power / exponent / factorial time constant