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$ ...