Big O Notation

Big O Notation is used to describe the time and space complexity of an algorithm as the input size grows. It shows how an algorithm's performance scales.

Common Notations

Growth Comparison

n=10:
O(1)     = 1
O(log n) = 3.3
O(n)     = 10
O(n log n)= 33
O(n²)    = 100
O(2ⁿ)    = 1024
O(n!)    = 3,628,800

n=100:
O(n)     = 100
O(n²)    = 10,000
O(2ⁿ)    = practically infinite

How to Analyze Code

O(1) - Constant

def get_first(arr):
    return arr[0]  # Always 1 operation

O(n) - Linear

def find_max(arr):
    max_val = arr[0]  # n comparisons
    for num in arr:
        if num > max_val:
            max_val = num
    return max_val

O(n²) - Quadratic

def has_duplicate(arr):
    for i in range(len(arr)):      # n times
        for j in range(i+1, len(arr)):  # n times
            if arr[i] == arr[j]:
                return True
    return False

O(log n) - Logarithmic

def binary_search(arr, target):
    low, high = 0, len(arr) - 1  # n divided by 2, repeatedly
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Space Complexity

# O(1) space
def sum_array(arr):
    total = 0
    for num in arr:
        total += num
    return total

# O(n) space
def create_copy(arr):
    return arr[:]

# O(n²) space
def create_matrix(n):
    return [[0] * n for _ in range(n)]

Amortized Analysis

Some operations are faster on average even though they are occasionally slow:

# list.append() - amortized O(1)
# Sometimes O(n) during a resize, but O(1) on average
arr = []
for i in range(1000):
    arr.append(i)  # Amortized O(1)

Common Patterns

# O(n) - single loop
for i in range(n):
    pass

# O(n²) - nested loop
for i in range(n):
    for j in range(n):
        pass

# O(n³) - triple nested
for i in range(n):
    for j in range(n):
        for k in range(n):
            pass

# O(log n) - divide by 2
while n > 1:
    n = n // 2

# O(n log n) - loop + divide
for i in range(n):
    j = 1
    while j < n:
        j *= 2

Big O helps you understand algorithmic efficiency. The Cheatsheet in the final chapter summarizes everything we've covered.