Big-O Complexity Analysis

Why Complexity Matters

Algorithm efficiency determines if code scales. A function that works on 100 items may time out on 1,000,000.

Big-O Notation

Big-O describes the worst-case growth rate of time or space as input size n grows.

Analyzing Code

O(1) — Constant

def get_first(lst):
    return lst[0]   # always one operation

def is_even(n):
    return n % 2 == 0  # regardless of n's size

O(n) — Linear

def find_max(lst):
    max_val = lst[0]
    for item in lst:      # n iterations
        if item > max_val:
            max_val = item
    return max_val

def sum_all(lst):
    return sum(lst)   # O(n) internally

O(n²) — Quadratic

def bubble_sort(lst):
    n = len(lst)
    for i in range(n):           # n iterations
        for j in range(n - i - 1):  # n iterations each
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]
    return lst
# Total: ~n² comparisons

def has_duplicate_naive(lst):
    for i in range(len(lst)):
        for j in range(i + 1, len(lst)):  # O(n²)
            if lst[i] == lst[j]:
                return True
    return False

# Better: O(n) with a set
def has_duplicate_fast(lst):
    return len(lst) != len(set(lst))  # O(n)

O(log n) — Logarithmic

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1       # discard left half
        else:
            right = mid - 1      # discard right half
    return -1

# Each iteration halves the search space
# 1,000,000 items → at most 20 iterations (log₂ 1,000,000 ≈ 20)

O(n log n) — Log-linear

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # T(n/2)
    right = merge_sort(arr[mid:])  # T(n/2)
    return merge(left, right)      # O(n)
# T(n) = 2T(n/2) + O(n) → O(n log n)

Space Complexity

# O(1) space — in-place
def reverse_inplace(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

# O(n) space — creates new list
def reverse_new(arr):
    return arr[::-1]   # new list of size n

# O(n) space — recursion stack
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)  # n frames on stack

# O(log n) space — binary search recursion
def binary_search_rec(arr, target, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_rec(arr, target, mid + 1, right)
    else:
        return binary_search_rec(arr, target, left, mid - 1)

Amortized Analysis

# Python list.append() is O(1) amortized
# Occasionally O(n) when resizing, but averages O(1)

# Example: dynamic array doubling
class DynamicArray:
    def __init__(self):
        self.data = [None] * 1
        self.size = 0
        self.capacity = 1

    def append(self, item):
        if self.size == self.capacity:
            self._resize()         # O(n) occasionally
        self.data[self.size] = item
        self.size += 1

    def _resize(self):
        self.capacity *= 2         # double capacity
        new_data = [None] * self.capacity
        for i in range(self.size):
            new_data[i] = self.data[i]
        self.data = new_data

Common Pitfalls

# PITFALL 1: Hidden O(n) in loops
lst = list(range(10000))

# O(n²) — 'in' on list is O(n)
for i in range(len(lst)):
    if i in lst:      # O(n) each time!
        pass

# O(n) — 'in' on set is O(1)
lst_set = set(lst)
for i in range(len(lst)):
    if i in lst_set:  # O(1) each time
        pass

# PITFALL 2: String concatenation in loop
# O(n²) — strings are immutable
s = ""
for i in range(1000):
    s += str(i)    # creates new string each time!

# O(n) — join
s = "".join(str(i) for i in range(1000))

Exercises

Exercise 1: Complexity Analysis

Determine the time complexity of each function:

def a(n):
    for i in range(n):
        for j in range(10):
            print(i, j)

def b(n):
    i = n
    while i > 1:
        i //= 2

def c(lst):
    seen = set()
    for x in lst:
        if x in seen:
            return True
        seen.add(x)
    return False

Solution:

a(n): O(n) — inner loop runs exactly 10 times (constant), so total = n * 10 = O(n)
b(n): O(log n) — i is halved each iteration
c(lst): O(n) — one pass, set operations are O(1)

Exercise 2: Optimize Pair Sum

Find if any two numbers in a list sum to a target.

# O(n²) version:
def has_pair_sum_slow(lst, target):
    for i in range(len(lst)):
        for j in range(i+1, len(lst)):
            if lst[i] + lst[j] == target:
                return True
    return False

# O(n) version using set:
def has_pair_sum_fast(lst, target):
    seen = set()
    for num in lst:
        complement = target - num
        if complement in seen:
            return True
        seen.add(num)
    return False