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.

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

We can see that the

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

Computer science - time complexity examples

Sorting functions by time complexity

Step by step guide

Categorizing the complexities

Constant time complexity

Log time complexity

Power / exponent / factorial time constant

新しい教材

教材を発見

トピックを見つける