Computer science - time complexity examples
- Didier Michel Joomun
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.
Categorizing the complexities
We now see that there are some groups of time complexities in our question :
- Powers, exponents and factorial