Common Complexity Scenarios

List of important complexities

In this lesson, we are going to study some common examples and handy formulas for solving time complexity problems.

The following list shows some common loop statements and how much time they take to execute:

$$$$

Simple for loop

for x in range(n):
    # statement(s) that take constant time

Running time complexity = $n$ = $O(n)$

Explanation: Python’s range(n) function returns an array that contains integers from 0 till n-1 ([0, 1, 2, …, n-1]). The in means that x is set equal to the numbers in this array at each iteration of the loop sequentially. So n is first 0, then 1, then 2, …, then n-1. This means the loop runs a total of $n$ times, hence the running time complexity is $n$.

$$$$

For loop with increments

for x in range(1,n,k):
    # statement(s) that take constant time

Running time complexity = $floor(\frac{n}{k})$ = $O(n)$

Explanation: With this Python statement, x is initially set equal to 1 and then gets set to values incremented by k until it reaches a number greater than or equal to n. In other words, x will be set to [$1, 1+k, 1+2k, 1+3k, \cdots, (1+mk) < n$]. It takes $floor(\frac{n}{k})$ time since there are that many numbers that x is set to. Also, note that in Python, changing the value of x within the loop would not affect the time complexity since x is initialized at every iteration unlike in other languages such as C++ where x is simply incremented/decremented/multiplied/divided. Try it for yourself!