Big O Notation - Time Complexity Explained With Real Code

1) Constant Time - O(1)

The work stays the same no matter how large the input grows.

Constant Time - O(1)

The amount of work does not change when the input gets bigger.

O(1)

# List
scores = [70, 85, 90]
scores.append(95)      # add to the back
scores.pop()           # remove from the back
scores[0]              # read by index
scores[-1] = 100       # write by index


# Dictionary / Set
ages = {}
ages["ana"] = 31       # insert or update
"ana" in ages          # membership check
ages.get("ana")        # lookup
del ages["ana"]        # delete

2) Logarithmic Time - O(log n)

Each step throws away a constant fraction of the remaining input, usually half.

Logarithmic Time - O(log n)

Every step cuts the remaining work by a constant factor, usually in half.

O(log n)

# Binary search on a sorted list
nums = [2, 5, 8, 12, 16, 23]
lo, hi = 0, len(nums) - 1
while lo <= hi:
    mid = (lo + hi) // 2
    if nums[mid] == 16:
        break
    elif nums[mid] < 16:
        lo = mid + 1
    else:
        hi = mid - 1

# Heap push and pop
import heapq
heap = []
heapq.heappush(heap, 7)
heapq.heappop(heap)

3) Linear Time - O(n)

The work grows in direct proportion to the size of the input.

Linear Time - O(n)

The work grows at the same rate as the input size.

O(n)

nums = [4, 1, 7]
total = sum(nums)      # visit every element
for x in nums:         # one pass
    print(x)

nums.insert(0, 9)      # shift everything right
nums.remove(7)         # search, then shift left
print(9 in nums)       # scan until found

seen = set(nums)       # build a set
copy = nums[:]         # copy the list

# a loop inside a loop can still be O(n)
# (two pointers that only move forward)

4) Square Root Time - O(√n)

The work grows with the square root of the input, which shows up when you only need to check up to √n.

Square Root Time - O(√n)

The work grows with the square root of the input size.

O(√n)

# Is n a prime number?
import math

def is_prime(n):
    if n < 2:
        return False
    for d in range(2, math.isqrt(n) + 1):
        if n % d == 0:
            return False
    return True

# Every divisor above √n pairs with
# one below it, so we stop at √n.
is_prime(97)

5) Loglinear Time - O(n log n)

Linear work repeated a logarithmic number of times, which is the cost of most efficient sorts.

Loglinear Time - O(n log n)

Linear work done once per level of a logarithmic process.

O(n log n)

# Built-in sort (Timsort)
nums = [5, 3, 9, 1, 4]
nums.sort()

# Heap sort
import heapq
heapq.heapify(nums)        # O(n)
ordered = []
while nums:
    ordered.append(heapq.heappop(nums))  # O(log n)

# Merge sort splits log n times and
# merges n elements at every level.

6) Two Inputs - O(n * m)

Two independent inputs of sizes n and m, where every element of the first input is paired with every element of the second input.

Two Inputs - O(n * m)

Each element of one input is paired with every element of another input.

O(n * m)

# Every pairing of two different lists
shirts = ["red", "blue"]
pants = ["jeans", "khaki", "black"]
for s in shirts:
    for p in pants:
        print(s, p)

# Visit every cell of a grid
grid = [[1, 2, 3],
        [4, 5, 6]]
for r in range(len(grid)):
    for c in range(len(grid[0])):
        print(grid[r][c])

7) Quadratic Time - O(n²)

The work grows with the square of the input size.

This usually comes from comparing every element with every other element of the same input. Two loops written one after the other are O(n) + O(n), which is still O(n).

Quadratic Time - O(n²)

The work grows with the square of the input size.

O(n²)

# Compare every pair in one list
nums = [3, 8, 1, 6]
for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
        print(nums[i], nums[j])

# Insertion sort
for i in range(1, len(nums)):
    j = i
    while j > 0 and nums[j - 1] > nums[j]:
        nums[j - 1], nums[j] = nums[j], nums[j - 1]
        j -= 1

8) Cubic Time - O(n³)

The work grows with the cube of the input size, typically from three nested loops over the same input.

Cubic Time - O(n³)

The work grows with the cube of the input size.

O(n³)

# Every triple of distinct indices
nums = [2, 7, 4, 1]
n = len(nums)
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            print(nums[i], nums[j], nums[k])

# Floyd-Warshall shortest paths
for k in range(n):
    for i in range(n):
        for j in range(n):
            pass  # relax dist[i][j] through k

9) Exponential Time - O(2ⁿ)

The work doubles every time the input grows by one element.

You see it when every element leads to a yes or no choice, such as listing all subsets of n items.

Exponential Time - O(2ⁿ)

The work doubles each time one more element is added.

O(2ⁿ)

# Every subset: each item is in or out
def subsets(nums, i=0, path=[]):
    if i == len(nums):
        print(path)
        return
    subsets(nums, i + 1, path + [nums[i]])
    subsets(nums, i + 1, path)

# Fibonacci without memoization
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

10) Factorial Time - O(n!)

The work grows with the factorial of the input size.

It appears when you produce every possible ordering of n distinct items.

Factorial Time - O(n!)

The work grows with the factorial of the input size.

O(n!)

# Every ordering of the items
def permutations(items, path=[]):
    if not items:
        print(path)
        return
    for i in range(len(items)):
        rest = items[:i] + items[i + 1:]
        permutations(rest, path + [items[i]])

permutations([1, 2, 3])
# n choices, then n - 1, then n - 2 ...
# n * (n - 1) * ... * 1 = n!

NOTES

Big O describes how the running time grows as the input gets larger, not how many seconds a program takes.
A constant time operation can still be slow if that constant is huge.