Complexity Analysis Deep Dive

📖 Introduction

Early in my programming journey, I thought Big O was just interview preparation—a hoop to jump through. But working on systems that process millions of records taught me otherwise. Understanding complexity analysis became essential when a "simple" feature suddenly took 30 minutes instead of 30 seconds, or when a memory spike crashed our production server.

This article goes beyond the basics to explore the nuances of algorithmic analysis: when average case matters more than worst case, how amortized analysis explains Python's list behavior, and practical techniques for benchmarking your code.

---

🎯 Asymptotic Analysis

Asymptotic analysis describes algorithm behavior as input approaches infinity. We focus on growth rate, not exact operations.

Big O, Big Ω, and Big Θ

def example_analysis(arr: list) -> int:
    """
    Find maximum in unsorted array.
    
    Big O:     O(n)  - At most n comparisons
    Big Ω:     Ω(n)  - At least n comparisons (must see all)
    Big Θ:     Θ(n)  - Exactly n-1 comparisons always
    
    Since O = Ω = Θ, this is a tight bound.
    """
    max_val = arr[0]
    for num in arr[1:]:  # n-1 iterations
        if num > max_val:
            max_val = num
    return max_val

Dropping Constants and Lower Terms

Big O focuses on dominant terms:

# All of these are O(n)
def example1(n):
    for i in range(n):          # n operations
        pass
    
def example2(n):
    for i in range(2 * n):      # 2n operations → O(n)
        pass
    
def example3(n):
    for i in range(n):          # n operations
        pass
    for j in range(n):          # + n operations
        pass                     # = 2n → O(n)

def example4(n):
    for i in range(n):          # n operations
        pass
    for j in range(100):        # + 100 operations
        pass                     # = n + 100 → O(n)

# Why we drop constants: scaling behavior

import time

def linear_fast(n):
    """n operations."""
    total = 0
    for i in range(n):
        total += i
    return total

def linear_slow(n):
    """5n operations - but still O(n)."""
    total = 0
    for i in range(n):
        total += i
        total += i
        total += i
        total += i
        total += i
    return total

def quadratic(n):
    """n² operations - different complexity class."""
    total = 0
    for i in range(n):
        for j in range(n):
            total += 1
    return total

# At n = 10,000:
# linear_fast: ~0.001s
# linear_slow: ~0.005s (5x slower, but scales same)
# quadratic:   ~10s (1000x slower, gets MUCH worse)

---

📊 Best, Worst, and Average Case

Different inputs can produce different performance for the same algorithm.

Linear Search Example

def linear_search(arr: list, target: int) -> int:
    """
    Search for target in unsorted array.
    
    Best Case:  O(1)  - Target is first element
    Worst Case: O(n)  - Target is last or not present
    Average Case: O(n/2) = O(n) - Target is in middle on average
    """
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1


# Different scenarios
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

# Best case: O(1)
linear_search(arr, 1)  # Found immediately

# Worst case: O(n)
linear_search(arr, 10)  # Check all elements
linear_search(arr, 99)  # Not found, check all

# Average case: O(n/2) → O(n)
# On average, we check half the elements

QuickSort Example

def quicksort(arr: list) -> list:
    """
    Divide and conquer sorting.
    
    Best Case:    O(n log n) - Balanced partitions
    Worst Case:   O(n²)      - Already sorted (poor pivot)
    Average Case: O(n log n) - Random data
    
    Space: O(log n) to O(n) depending on implementation
    """
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]  # Middle element as pivot
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    return quicksort(left) + middle + quicksort(right)


# Worst case: already sorted array with first/last as pivot
# [1, 2, 3, 4, 5] with pivot=1:
#   left=[], right=[2,3,4,5]
#   Partitions of size 0 and n-1 → O(n²)

# Best case: balanced partitions
# [3, 1, 4, 1, 5, 9, 2, 6]
#   Each partition roughly halves the array → O(n log n)

When Each Case Matters

Algorithm	When to Care About
Binary Search	Always O(log n), case doesn't matter
Hash Table	Average O(1), but worst O(n) matters for security
QuickSort	Average O(n log n), but worst O(n²) matters for adversarial inputs
Linear Search	Usually average/worst matters, best is rare

# Hash table worst case attack
# An attacker could craft inputs with same hash → O(n) lookup

# Python 3.3+ uses randomized hashing to prevent this
hash("test")  # Different result each Python session

---

⚡ Amortized Analysis

Amortized analysis averages cost over a sequence of operations, not individual ones.

Dynamic Array (Python List)

# Python lists over-allocate to make appends efficient

import sys

lst = []
last_size = 0

for i in range(100):
    lst.append(i)
    current_size = sys.getsizeof(lst)
    
    if current_size != last_size:
        print(f"Length {len(lst):3d}: {current_size} bytes (resized)")
        last_size = current_size

# Output shows resize pattern:
# Length   1: 88 bytes (resized)
# Length   5: 120 bytes (resized)
# Length   9: 184 bytes (resized)
# Length  17: 248 bytes (resized)
# ...
# Capacity roughly doubles each time

Why Append is O(1) Amortized

class DynamicArray:
    """
    Simplified dynamic array implementation.
    
    Append:
    - Worst case: O(n) when resize needed
    - Amortized: O(1) because resizes are rare
    
    Proof:
    - Insert n elements
    - Resize at: 1, 2, 4, 8, ..., n (log n times)
    - Total copy operations: 1 + 2 + 4 + ... + n ≈ 2n
    - Cost per insert: 2n / n = O(1)
    """
    
    def __init__(self):
        self.capacity = 1
        self.size = 0
        self.array = [None] * self.capacity
    
    def append(self, item):
        if self.size == self.capacity:
            self._resize(2 * self.capacity)
        
        self.array[self.size] = item
        self.size += 1
    
    def _resize(self, new_capacity: int):
        """O(n) - but happens infrequently."""
        new_array = [None] * new_capacity
        for i in range(self.size):
            new_array[i] = self.array[i]
        self.array = new_array
        self.capacity = new_capacity
    
    def __getitem__(self, index: int):
        """O(1) - direct index access."""
        if 0 <= index < self.size:
            return self.array[index]
        raise IndexError("Index out of range")

Amortized Analysis Methods

1. Aggregate Method

# Sum all costs, divide by n operations

# Example: Stack with multipop
class MultiPopStack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        """O(1)"""
        self.items.append(item)
    
    def pop(self):
        """O(1)"""
        return self.items.pop() if self.items else None
    
    def multipop(self, k: int):
        """O(min(k, n)) - pop up to k items."""
        popped = []
        for _ in range(min(k, len(self.items))):
            popped.append(self.items.pop())
        return popped

# Sequence of n push + n multipop(n):
# Total pops = n (each item popped at most once)
# Amortized cost per operation = O(n) / O(n) = O(1)

2. Accounting Method

# Assign "credits" to cheap operations to pay for expensive ones

# Example: Binary counter
class BinaryCounter:
    """
    Count from 0 upward in binary.
    
    Increment seems expensive (many bit flips), but amortized O(1).
    
    Accounting:
    - Charge $2 for each 0→1 flip
    - Use $1 to flip, save $1 as credit
    - When 1→0, use saved credit
    - Total cost for n increments: $2n → O(1) amortized
    """
    
    def __init__(self, bits: int = 8):
        self.bits = [0] * bits
    
    def increment(self) -> list:
        i = 0
        # Flip trailing 1s to 0s
        while i < len(self.bits) and self.bits[i] == 1:
            self.bits[i] = 0
            i += 1
        
        # Flip first 0 to 1
        if i < len(self.bits):
            self.bits[i] = 1
        
        return self.bits.copy()
    
    def value(self) -> int:
        return sum(b * (2 ** i) for i, b in enumerate(self.bits))


counter = BinaryCounter(4)
for _ in range(16):
    bits = counter.increment()
    print(f"{counter.value():2d}: {bits[::-1]}")

---

🔬 Practical Benchmarking

Theory is important, but real-world performance depends on constants and hardware.

Using timeit

import timeit

def measure_algorithms():
    """Compare actual runtime of different approaches."""
    
    setup = """
import random
data = [random.randint(1, 1000) for _ in range(10000)]
target = data[5000]
    """
    
    # Linear search
    linear_time = timeit.timeit(
        stmt="data.index(target)",
        setup=setup,
        number=1000
    )
    
    # Binary search (on sorted data)
    binary_setup = setup + """
data.sort()
import bisect
    """
    binary_time = timeit.timeit(
        stmt="bisect.bisect_left(data, target)",
        setup=binary_setup,
        number=1000
    )
    
    print(f"Linear search: {linear_time:.4f}s")
    print(f"Binary search: {binary_time:.4f}s")
    print(f"Speedup: {linear_time / binary_time:.1f}x")


# Output example:
# Linear search: 0.1234s
# Binary search: 0.0012s
# Speedup: 102.8x

Memory Profiling

import sys
from typing import List

def compare_memory():
    """Compare memory usage of different structures."""
    
    n = 10000
    
    # List
    lst = list(range(n))
    
    # Tuple
    tpl = tuple(range(n))
    
    # Set
    st = set(range(n))
    
    # Dict
    dct = {i: i for i in range(n)}
    
    print(f"List:  {sys.getsizeof(lst):,} bytes")
    print(f"Tuple: {sys.getsizeof(tpl):,} bytes")
    print(f"Set:   {sys.getsizeof(st):,} bytes")
    print(f"Dict:  {sys.getsizeof(dct):,} bytes")


# Typical output:
# List:  85,176 bytes
# Tuple: 80,048 bytes
# Set:   524,504 bytes
# Dict:  295,016 bytes

Scaling Tests

import time
from typing import Callable, List

def measure_scaling(
    func: Callable,
    sizes: List[int],
    setup: Callable = None
) -> List[tuple]:
    """Measure function runtime at different input sizes."""
    
    results = []
    
    for n in sizes:
        # Setup data
        if setup:
            data = setup(n)
        else:
            data = list(range(n))
        
        # Measure
        start = time.perf_counter()
        func(data)
        elapsed = time.perf_counter() - start
        
        results.append((n, elapsed))
        print(f"n={n:>8,}: {elapsed:.4f}s")
    
    return results


def detect_complexity(results: List[tuple]) -> str:
    """Estimate complexity from timing results."""
    
    import math
    
    # Compare ratios between successive sizes
    ratios = []
    for i in range(1, len(results)):
        n1, t1 = results[i - 1]
        n2, t2 = results[i]
        
        if t1 > 0:
            time_ratio = t2 / t1
            size_ratio = n2 / n1
            ratios.append(time_ratio / size_ratio)
    
    avg_ratio = sum(ratios) / len(ratios) if ratios else 1
    
    # Classify based on average ratio
    if avg_ratio < 0.2:
        return "O(log n)"
    elif avg_ratio < 1.5:
        return "O(n)"
    elif avg_ratio < 5:
        return "O(n log n)"
    elif avg_ratio < 15:
        return "O(n²)"
    else:
        return "O(n²) or worse"


# Example usage
def bubble_sort(arr: list) -> list:
    arr = arr.copy()
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr


sizes = [100, 200, 400, 800, 1600]
results = measure_scaling(bubble_sort, sizes)
complexity = detect_complexity(results)
print(f"\nDetected complexity: {complexity}")

---

📐 Common Patterns

Nested Loops

# O(n²) - Both loops depend on n
def pattern_n_squared(n: int):
    count = 0
    for i in range(n):
        for j in range(n):
            count += 1
    return count  # Returns n²


# O(n²) - Inner loop shrinks, but still quadratic
def pattern_triangle(n: int):
    count = 0
    for i in range(n):
        for j in range(i, n):  # n-i iterations
            count += 1
    return count  # Returns n(n+1)/2 ≈ n²/2 → O(n²)


# O(n) - Inner loop is constant
def pattern_linear(n: int):
    count = 0
    for i in range(n):
        for j in range(100):  # Always 100 iterations
            count += 1
    return count  # Returns 100n → O(n)

Logarithmic Patterns

# O(log n) - Divide by 2 each iteration
def log_pattern(n: int) -> int:
    count = 0
    while n > 1:
        n //= 2
        count += 1
    return count


# O(log n) - Multiply by 2 until reaching n
def log_pattern_up(n: int) -> int:
    count = 0
    i = 1
    while i < n:
        i *= 2
        count += 1
    return count


# O(n log n) - Linear outer, log inner
def n_log_n_pattern(n: int) -> int:
    count = 0
    for i in range(n):        # n iterations
        j = n
        while j > 1:          # log n iterations
            j //= 2
            count += 1
    return count

Recursive Complexity

# O(n) - Single recursive call
def linear_recursion(n: int) -> int:
    if n <= 0:
        return 0
    return 1 + linear_recursion(n - 1)


# O(2^n) - Two recursive calls
def exponential_recursion(n: int) -> int:
    if n <= 1:
        return 1
    return exponential_recursion(n - 1) + exponential_recursion(n - 2)


# O(n log n) - Divide and conquer
def merge_sort_pattern(arr: list) -> list:
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort_pattern(arr[:mid])    # T(n/2)
    right = merge_sort_pattern(arr[mid:])   # T(n/2)
    
    # O(n) merge
    return merge(left, right)


def merge(left: list, right: list) -> list:
    """O(n) merge operation."""
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

---

🧮 Master Theorem

For divide-and-conquer recurrences: T(n) = aT(n/b) + f(n)

Common Examples

# Binary Search: T(n) = T(n/2) + O(1)
# a=1, b=2, f(n)=1
# log_2(1) = 0, f(n) = Θ(n^0) = Θ(1)
# Case 2 → T(n) = Θ(log n)

def binary_search(arr: list, target: int) -> int:
    """T(n) = T(n/2) + O(1) → O(log n)"""
    if not arr:
        return -1
    
    mid = len(arr) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr[mid + 1:], target)
    else:
        return binary_search(arr[:mid], target)


# Merge Sort: T(n) = 2T(n/2) + O(n)
# a=2, b=2, f(n)=n
# log_2(2) = 1, f(n) = Θ(n^1)
# Case 2 → T(n) = Θ(n log n)

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


# Strassen's Matrix Multiplication: T(n) = 7T(n/2) + O(n²)
# a=7, b=2, f(n)=n²
# log_2(7) ≈ 2.807, f(n) = O(n^2) = O(n^(2.807 - 0.807))
# Case 1 → T(n) = Θ(n^2.807) ≈ O(n^2.81)

---

📝 Practice Exercises

Exercise 1: Analyze These Functions

def func1(n: int) -> int:
    total = 0
    i = 1
    while i < n:
        total += i
        i *= 2
    return total

def func2(n: int) -> int:
    if n <= 1:
        return 1
    return func2(n - 1) + func2(n - 1)

def func3(n: int) -> int:
    total = 0
    for i in range(n):
        j = 1
        while j < n:
            total += 1
            j *= 2
    return total

Solutions

1. func1: O(log n) - i doubles each iteration

2. func2: O(2^n) - two recursive calls at each level

3. func3: O(n log n) - outer O(n), inner O(log n)

Exercise 2: Identify Best/Worst/Average

def find_pair(arr: list, target: int) -> tuple:
    """Find two numbers that sum to target."""
    seen = {}
    for i, num in enumerate(arr):
        complement = target - num
        if complement in seen:
            return (seen[complement], i)
        seen[num] = i
    return None

Solution

• Best Case: O(1) - First two elements sum to target

• Worst Case: O(n) - Pair is at end or doesn't exist

• Average Case: O(n) - On average, scan most of array

Space: O(n) in all cases (hash map stores elements)

Exercise 3: Optimize

def find_duplicates(arr: list) -> list:
    """Current: O(n²) time, O(n) space."""
    duplicates = []
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j] and arr[i] not in duplicates:
                duplicates.append(arr[i])
    return duplicates

# Rewrite to achieve O(n) time

Solution

def find_duplicates_optimized(arr: list) -> list:
    """O(n) time, O(n) space."""
    seen = set()
    duplicates = set()
    
    for num in arr:
        if num in seen:
            duplicates.add(num)
        seen.add(num)
    
    return list(duplicates)

---

🔑 Key Takeaways

1. Asymptotic analysis focuses on growth rate, ignoring constants

2. Best/worst/average cases matter for different scenarios

3. Amortized analysis explains "expensive but rare" operations

4. Practical benchmarking reveals real-world performance

5. Master theorem solves divide-and-conquer recurrences

6. Pattern recognition speeds up complexity analysis

---

🚀 What's Next?

In the next article, we'll explore recursion fundamentals:

• How the call stack works

• Designing base cases

• Memoization for optimization

• Converting iteration to recursion and back

Next: Article 3 - Recursion Fundamentals

---

📚 References

• Cormen, T. H., et al. "Introduction to Algorithms" - Chapter 3 & 4

• Sedgewick, R. "Algorithms" - Analysis of Algorithms

• Python Wiki: TimeComplexity