Big-O Notation

The Big-O notation is about the performance or time complexity of an algorithm. It describes the worst-case scenario, the execution time required, and the space used by an algorithm. You can get the more explanation here and the cheat sheet here.

O(1) - Constant Time

It only takes a single step.

z = x + y

O(log n) - Logarithmic Time

The number of steps decreases in every step by some factor.

x = 1
while x < 10:
    print(x)
    x *= 2

O(n) - Linear Time

The running time increases linearly with the size of the input.

for x in range(10):
    print(x)

O(n log n) - Quasilinear Time

The result of performing an O(log n) operation in n times.

for x in range(10):
    x = 1
    while x < 10:
        print(x)
        x *= 2

O(n2) - Quadratic Time

The result of performing an O(n) operation in n times.

for x in range(10):
    for x in range(10):
        print(x)

O(2n) - Exponential Time

This is common in situations when you traverse all the nodes in a binary tree.

def fibonacci(x):
    if x <= 1:
        return x
    return fibonacci(x - 2) + fibonacci(x - 1)

O(n!) - Factorial Time

This is common in generating permutations.

def factorial(x):
    for i in range(x):
        factorial(x - 1)