Python Big-O Notation Practice Problems & Exercises

Practice: Big-O Notation

12 problems4 Easy5 Medium3 Hard⏱ 50–70 min

← Back to lesson

---

Easy

#1Name That ComplexityEasy

big-oidentificationtime-complexity

Identify the Big-O complexity of each function below. Print your answers, then check.

Python

def func_a(lst):
    """Three operations, regardless of list size."""
    if len(lst) == 0:
        return None
    first = lst[0]
    last = lst[-1]
    return first + last

def func_b(lst):
    """Sum every element."""
    total = 0
    for item in lst:
        total += item
    return total

def func_c(lst):
    """Check every pair."""
    pairs = []
    for i in range(len(lst)):
        for j in range(len(lst)):
            pairs.append((lst[i], lst[j]))
    return pairs

def func_d(lst, target):
    """Binary search on a sorted list."""
    low, high = 0, len(lst) - 1
    while low <= high:
        mid = (low + high) // 2
        if lst[mid] == target:
            return mid
        elif lst[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# Verify with operation counters
import time

n = 10000
data = list(range(n))

start = time.perf_counter()
func_a(data)
t_a = time.perf_counter() - start

start = time.perf_counter()
func_b(data)
t_b = time.perf_counter() - start

start = time.perf_counter()
func_d(data, n - 1)
t_d = time.perf_counter() - start

print("func_a: O(1)")
print("func_b: O(n)")
print("func_c: O(n²)")
print("func_d: O(log n)")
print(f"\nTiming confirms relative speeds:")
print(f"  func_a: {t_a:.8f}s (constant)")
print(f"  func_b: {t_b:.8f}s (linear)")
print(f"  func_d: {t_d:.8f}s (logarithmic)")

Solution

func_a: O(1)
func_b: O(n)
func_c: O(n²)
func_d: O(log n)

Analysis:

• func_a — O(1): Accesses the first and last elements by index. No loops, no recursion. The number of operations is constant regardless of input size.
• func_b — O(n): A single loop iterates through every element once. Doubling the input doubles the work.
• func_c — O(n²): Two nested loops, each iterating n times. 10x the input means 100x the work. This is the classic "check every pair" pattern.
• func_d — O(log n): Binary search cuts the remaining search space in half each iteration. For 1,000,000 elements, it needs at most ~20 comparisons.

Expected Output

func_a: O(1)\nfunc_b: O(n)\nfunc_c: O(n²)\nfunc_d: O(log n)

Hints

Hint 1: Count how many times the core operation runs relative to the input size n. Does it stay fixed, grow linearly, grow quadratically, or halve each step?

Hint 2: func_a does the same 3 operations regardless of n. func_b loops n times. func_c has a loop inside a loop. func_d halves the search space each iteration.

#2Dict vs List LookupEasy

dictlistlookupO(1)-vs-O(n)

Compare list search vs dict lookup performance. Time both operations on the same data, then explain the Big-O difference.

Python

import time

n = 100_000
data_list = list(range(n))
data_dict = {i: True for i in range(n)}
target = n - 1  # Worst case for list: last element

# List search — O(n)
start = time.perf_counter()
found_list = target in data_list
list_time = time.perf_counter() - start

# Dict lookup — O(1)
start = time.perf_counter()
found_dict = target in data_dict
dict_time = time.perf_counter() - start

print(f"List search ({n} items): {found_list}")
print(f"Dict lookup ({n} items): {found_dict}")
print(f"List is O(n), Dict is O(1)")
print(f"List time: {list_time:.6f}s")
print(f"Dict time: {dict_time:.6f}s")
print(f"Dict is ~{list_time / max(dict_time, 1e-9):.0f}x faster")

Solution

def find_in_list(lst, target):
    """O(n) — must scan every element in the worst case."""
    for item in lst:
        if item == target:
            return True
    return False

def find_in_dict(d, target_key):
    """O(1) average — hash table lookup."""
    return target_key in d

Why the massive speed difference:

• List search is O(n): Python walks through every element from index 0 until it finds the target or reaches the end. For 100,000 elements with the target at the end, that is 100,000 comparisons.
• Dict lookup is O(1) average: Python hashes the key, computes the bucket index, and checks 1-2 slots. Regardless of whether the dict has 100 or 100,000,000 entries, the lookup takes roughly the same time.

When to use which: If you are checking membership repeatedly, convert your list to a set or dict first. The one-time O(n) conversion cost pays for itself quickly.

Starter Code

def find_in_list(lst, target):
    """Search for target in a list. What's the Big-O?"""
    for item in lst:
        if item == target:
            return True
    return False

def find_in_dict(d, target_key):
    """Search for target_key in a dict. What's the Big-O?"""
    return target_key in d

Expected Output

List search (100000 items): True\nDict lookup (100000 items): True\nList is O(n), Dict is O(1)\nList time: ~slow\nDict time: ~instant

Hints

Hint 1: Think about the underlying data structure. A list search must check every element. A dict uses a hash table.

Hint 2: The `in` operator on a list is O(n) — it does a linear scan. The `in` operator on a dict is O(1) on average — it computes a hash and jumps to the right bucket.

#3Which Function Wins at Scale?Easy

big-ocomparisonscaling

Two functions compute the same result — the sum of numbers from 1 to n. Predict which one is faster for large n and explain why.

Python

import time

def approach_a(n):
    """Loop through every number."""
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

def approach_b(n):
    """Mathematical formula."""
    return n * (n + 1) // 2

# Verify both give the same result
n = 100
print(f"n={n}: approach_a={approach_a(n)}, approach_b={approach_b(n)}")

n = 10_000
assert approach_a(n) == approach_b(n)
print(f"n={n}: Both give same results")

# Time them at scale
n = 1_000_000

start = time.perf_counter()
approach_a(n)
time_a = time.perf_counter() - start

start = time.perf_counter()
approach_b(n)
time_b = time.perf_counter() - start

print(f"approach_a is O(n), approach_b is O(1)")
print(f"At n={n}, approach_b is dramatically faster")
print(f"  approach_a: {time_a:.6f}s")
print(f"  approach_b: {time_b:.8f}s")
print(f"  Speedup: {time_a / max(time_b, 1e-9):.0f}x")

Solution

• approach_a is O(n): It loops through every integer from 1 to n. Doubling n doubles the time.
• approach_b is O(1): It uses the formula n * (n + 1) // 2 — a single multiplication, one addition, and one division. The time is constant regardless of n.

Key insight: The best optimization is often mathematical, not algorithmic. Before writing a loop, ask: "Is there a closed-form formula?" Gauss famously discovered this formula as a child — the sum of 1 to 100 is 100 * 101 / 2 = 5050.

When this matters in practice: Aggregation queries, financial calculations, statistics. Replacing an O(n) loop with an O(1) formula can turn a minutes-long computation into a microsecond.

Expected Output

n=100: approach_a=5050, approach_b=5050\nn=10000: Both give same results\napproach_a is O(n), approach_b is O(1)\nAt n=1000000, approach_b is dramatically faster

Hints

Hint 1: One function loops through every number. The other uses a direct formula. Think about how each scales when n goes from 1,000 to 1,000,000.

Hint 2: The mathematical formula for the sum of 1 to n is n*(n+1)/2 — it computes the answer in a single step regardless of n.

#4Count the OperationsEasy

nested-loopsoperation-countingO(n²)

A nested loop does not always mean exactly n*n operations. Count the exact number of operations in the loop below, find the formula, and confirm it is still O(n²).

Python

def count_operations(n):
    ops = 0
    for i in range(n):
        for j in range(i + 1, n):
            ops += 1
    return ops

# Test at different sizes
for n in [5, 10, 100]:
    actual = count_operations(n)
    formula = n * (n - 1) // 2
    print(f"n={n}: operations={actual}, formula={formula}")

print(f"Pattern: n*(n-1)/2 which is O(n²)")

# Show the growth rate is quadratic
import time
for n in [1000, 2000, 4000]:
    start = time.perf_counter()
    count_operations(n)
    elapsed = time.perf_counter() - start
    print(f"n={n}: {elapsed:.4f}s")
print("Each doubling of n roughly 4x the time — confirms O(n²)")

Solution

def count_operations(n):
    ops = 0
    for i in range(n):
        for j in range(i + 1, n):
            ops += 1
    return ops

# The exact count is n*(n-1)/2

Detailed counting:

The inner loop runs (n - i - 1) times for each value of i:

• i=0: inner loop runs (n-1) times
• i=1: inner loop runs (n-2) times
• i=2: inner loop runs (n-3) times
• ...
• i=n-2: inner loop runs 1 time
• i=n-1: inner loop runs 0 times

Total = (n-1) + (n-2) + ... + 1 + 0 = n(n-1)/2

Why it is still O(n²): In Big-O, we drop constants and lower-order terms. n(n-1)/2 = n²/2 - n/2. The dominant term is n²/2, and we drop the 1/2 constant, giving O(n²).

This pattern appears everywhere: checking all unique pairs, triangle iteration in dynamic programming, the inner loop of bubble sort and selection sort.

Starter Code

def count_operations(n):
    """Count exactly how many times the inner operation runs."""
    ops = 0
    for i in range(n):
        for j in range(i + 1, n):
            ops += 1  # Count this operation
    return ops

Expected Output

n=5:  operations=10,  formula=10\nn=10: operations=45,  formula=45\nn=100: operations=4950, formula=4950\nPattern: n*(n-1)/2 which is O(n²)

Hints

Hint 1: The inner loop does not always run n times. For each i, it runs (n - i - 1) times. Sum those up across all values of i.

Hint 2: The total is (n-1) + (n-2) + ... + 1 + 0 = n*(n-1)/2. This is still O(n²) because the leading term is n²/2.

---

Medium

#5Optimize the Duplicate FinderMedium

optimizationsetO(n²)-to-O(n)

The has_duplicates_slow function uses a nested loop to check every pair — O(n²). Rewrite it as has_duplicates_fast that runs in O(n) using a set.

Python

import time

def has_duplicates_slow(lst):
    for i in range(len(lst)):
        for j in range(i + 1, len(lst)):
            if lst[i] == lst[j]:
                return True
    return False

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

# Verify correctness
test_cases = [
    [1, 2, 3, 4, 5],       # No duplicates
    [1, 2, 3, 2, 5],       # Has duplicate
    [],                      # Empty
    [1],                     # Single element
    [1, 1],                  # Duplicate pair
]

all_pass = True
for tc in test_cases:
    if has_duplicates_slow(tc) != has_duplicates_fast(tc):
        all_pass = False
        print(f"MISMATCH on {tc}")

print(f"Slow result: {has_duplicates_slow([1,2,3,2])}, Fast result: {has_duplicates_fast([1,2,3,2])}")
print(f"Results match on all tests!" if all_pass else "SOME TESTS FAILED")

# Time comparison
n = 20000
data = list(range(n))  # Worst case: no duplicates, must check all
start = time.perf_counter()
has_duplicates_slow(data)
slow_time = time.perf_counter() - start

start = time.perf_counter()
has_duplicates_fast(data)
fast_time = time.perf_counter() - start

print(f"Slow (O(n²)): {slow_time:.4f}s")
print(f"Fast (O(n)):  {fast_time:.6f}s")
print(f"Speedup: {slow_time / max(fast_time, 1e-9):.0f}x")

Solution

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

Why O(n):

• We iterate through the list once: n steps.
• Each in check on a set is O(1) average (hash table lookup).
• Each add to a set is O(1) average.
• Total: n * O(1) = O(n).

Space trade-off: The O(n²) version uses O(1) extra space. The O(n) version uses O(n) extra space for the set. This is a classic time-space trade-off — you spend memory to save time.

Even faster one-liner: len(lst) != len(set(lst)) — but this always processes the entire list, even if the first two elements are duplicates. The explicit loop can short-circuit early.

Starter Code

def has_duplicates_slow(lst):
    """O(n²) — checks every pair."""
    for i in range(len(lst)):
        for j in range(i + 1, len(lst)):
            if lst[i] == lst[j]:
                return True
    return False

def has_duplicates_fast(lst):
    """Your task: rewrite to O(n) using a set."""
    pass

Expected Output

Slow result: True, Fast result: True\nResults match on all tests!\nSlow (O(n²)): ~slow\nFast (O(n)):  ~fast

Hints

Hint 1: A set has O(1) lookup. If you walk through the list once and check each element against a set of already-seen elements, the total is O(n).

Hint 2: For each element: check if it is in the seen set (O(1)), if yes return True, if no add it to the set (O(1)). One pass through the list = O(n) total.

#6Binary Search with Operation CounterMedium

binary-searchO(log-n)implementation

Implement binary search that also counts how many comparisons it makes. Verify that the count is approximately log2(n).

Python

import math

def binary_search_counted(sorted_list, target):
    comparisons = 0
    low, high = 0, len(sorted_list) - 1

    while low <= high:
        mid = (low + high) // 2
        comparisons += 1

        if sorted_list[mid] == target:
            return mid, comparisons
        elif sorted_list[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1, comparisons

# Test on a large sorted list
n = 1_000_000
data = list(range(n))

idx, comps = binary_search_counted(data, 7)
print(f"Found 7 at index {idx}, comparisons: {comps}")

idx, comps = binary_search_counted(data, n - 1)
print(f"Found {n-1} at index {idx}, comparisons: {comps}")

idx, comps = binary_search_counted(data, -5)
print(f"Not found {idx}, comparisons: {comps}")

print(f"log2({n}) = {math.log2(n):.2f} — matches!")

# Show comparison counts at different sizes
print("\nComparison counts at different sizes:")
for size in [100, 1_000, 10_000, 100_000, 1_000_000]:
    test_data = list(range(size))
    _, c = binary_search_counted(test_data, size // 3)
    print(f"  n={size:>10,}: comparisons={c:>3}, log2(n)={math.log2(size):.1f}")

Solution

def binary_search_counted(sorted_list, target):
    comparisons = 0
    low, high = 0, len(sorted_list) - 1

    while low <= high:
        mid = (low + high) // 2
        comparisons += 1

        if sorted_list[mid] == target:
            return mid, comparisons
        elif sorted_list[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1, comparisons

Why O(log n):

Each iteration eliminates half the remaining elements:

• Start: n elements
• After 1 comparison: n/2 elements
• After 2 comparisons: n/4 elements
• After k comparisons: n/2^k elements
• We stop when n/2^k = 1, so k = log2(n)

For 1,000,000 elements, log2(1,000,000) is about 20. That means binary search finds any element (or confirms it is missing) in at most 20 comparisons. A linear search would need up to 1,000,000 comparisons.

The catch: Binary search requires the input to be sorted. Sorting costs O(n log n), so it only pays off when you search the same data multiple times.

Starter Code

def binary_search_counted(sorted_list, target):
    """Return (index, num_comparisons) or (-1, num_comparisons)."""
    comparisons = 0
    low, high = 0, len(sorted_list) - 1
    # Your implementation here
    pass

Expected Output

Found 7 at index 7, comparisons: ~13-14\nFound 999999 at index 999999, comparisons: ~20\nNot found -1, comparisons: ~20\nlog2(1000000) = 19.93 — matches!

Hints

Hint 1: Binary search repeatedly halves the search space. Compare the target with the middle element — go left if smaller, go right if larger.

Hint 2: Count every comparison with the middle element. The total should be close to log2(n). For 1,000,000 elements, that is about 20 comparisons.

#7Flatten the Triple NestMedium

optimizationnested-loopsO(n³)-to-O(n)

The three_sum_slow function uses three nested loops — O(n³). Rewrite it as three_sum_fast using sorting + two pointers to achieve O(n²).

Python

import time

def three_sum_slow(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == target:
                    return (nums[i], nums[j], nums[k])
    return None

def three_sum_fast(nums, target):
    nums_sorted = sorted(nums)  # O(n log n)
    n = len(nums_sorted)

    for i in range(n - 2):
        left, right = i + 1, n - 1
        need = target - nums_sorted[i]

        while left < right:
            pair_sum = nums_sorted[left] + nums_sorted[right]
            if pair_sum == need:
                return (nums_sorted[i], nums_sorted[left], nums_sorted[right])
            elif pair_sum < need:
                left += 1
            else:
                right -= 1

    return None

# Correctness check
test = [2, 7, 4, 1, 10, 3, 8, 5]
target = 15
print(f"Slow: {three_sum_slow(test, target)}, Fast: {three_sum_fast(test, target)}")

# Performance comparison
import random
random.seed(42)
n = 2000
data = random.sample(range(n * 10), n)
target = data[0] + data[n // 2] + data[-1]

start = time.perf_counter()
three_sum_slow(data, target)
slow_time = time.perf_counter() - start

start = time.perf_counter()
three_sum_fast(data, target)
fast_time = time.perf_counter() - start

print(f"Slow (O(n³)): {slow_time:.4f}s")
print(f"Fast (O(n²)): {fast_time:.6f}s")
print(f"Speedup: {slow_time / max(fast_time, 1e-9):.0f}x")

Solution

def three_sum_fast(nums, target):
    nums_sorted = sorted(nums)  # O(n log n)
    n = len(nums_sorted)

    for i in range(n - 2):          # O(n) outer loop
        left, right = i + 1, n - 1
        need = target - nums_sorted[i]

        while left < right:          # O(n) two-pointer scan
            pair_sum = nums_sorted[left] + nums_sorted[right]
            if pair_sum == need:
                return (nums_sorted[i], nums_sorted[left], nums_sorted[right])
            elif pair_sum < need:
                left += 1
            else:
                right -= 1

    return None

Complexity breakdown:

• Sorting: O(n log n)
• Outer loop: O(n)
• Inner two-pointer scan: O(n) per outer iteration
• Total: O(n log n) + O(n) * O(n) = O(n²)

Why two pointers work: On a sorted array, if nums[left] + nums[right] is too small, increasing left increases the sum. If it is too large, decreasing right decreases the sum. This eliminates the need for an inner nested loop.

Real-world note: This is LeetCode problem #15 (3Sum). The two-pointer technique after sorting is one of the most common interview optimization patterns.

Starter Code

def three_sum_slow(nums, target):
    """O(n³) — find if any three numbers sum to target."""
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == target:
                    return (nums[i], nums[j], nums[k])
    return None

def three_sum_fast(nums, target):
    """Your task: reduce complexity using sorting + two pointers."""
    pass

Expected Output

Slow: (1, 4, 10), Fast: (1, 4, 10)\nSlow time: ~slow\nFast time: ~fast

Hints

Hint 1: Sort the array first (O(n log n)). Then for each element, use the two-pointer technique on the remaining elements to find a pair that sums to (target - element).

Hint 2: Two pointers: start one at the left and one at the right of the remaining subarray. If the sum is too small, move the left pointer right. If too large, move the right pointer left. This is O(n) per element, O(n²) total — much better than O(n³).

#8Recursive vs Iterative FibonacciMedium

recursionfibonacciO(2^n)-vs-O(n)

Analyze the time complexity of recursive vs iterative Fibonacci. Add call counters to both and compare.

Python

import time

call_count = 0

def fib_recursive(n):
    global call_count
    call_count += 1
    if n <= 1:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)

def fib_iterative(n):
    steps = 0
    if n <= 1:
        return n, steps
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
        steps += 1
    return b, steps

# Compare at n=30
n = 30

call_count = 0
start = time.perf_counter()
result_r = fib_recursive(n)
time_r = time.perf_counter() - start
calls_r = call_count

start = time.perf_counter()
result_i, steps_i = fib_iterative(n)
time_i = time.perf_counter() - start

print(f"fib_recursive({n}): {result_r}")
print(f"fib_iterative({n}): {result_i}")
print(f"Recursive calls for n={n}: {calls_r:,}")
print(f"Iterative steps for n={n}: {steps_i}")
print(f"Recursive: O(2^n), Iterative: O(n)")
print(f"\nRecursive time: {time_r:.4f}s")
print(f"Iterative time: {time_i:.8f}s")
print(f"Speedup: {time_r / max(time_i, 1e-9):.0f}x")

# Show exponential growth of recursive calls
print("\nRecursive call counts (doubles each step):")
for test_n in [10, 15, 20, 25, 30]:
    call_count = 0
    fib_recursive(test_n)
    print(f"  n={test_n}: {call_count:>10,} calls")

Solution

Recursive Fibonacci is O(2^n):

Each call spawns two more calls. The call tree looks like this:

                  fib(5)
                /        \
           fib(4)        fib(3)
          /      \       /     \
       fib(3)  fib(2)  fib(2) fib(1)
       /    \
    fib(2) fib(1)

The number of calls roughly doubles with each increment of n. For n=30, there are about 2.7 million calls. For n=50, it would take minutes. For n=100, it would not finish in your lifetime.

Iterative Fibonacci is O(n):

A single loop from 2 to n, with exactly n-1 additions. For n=30, that is 28 additions — done in microseconds.

The core problem: Recursive Fibonacci recomputes the same values exponentially many times. fib(3) is computed in multiple branches, fib(2) even more. This is the textbook example of why naive recursion can be catastrophically slow — and why memoization or dynamic programming exists.

Expected Output

fib_recursive(30): 832040\nfib_iterative(30): 832040\nRecursive calls for n=30: huge\nIterative steps for n=30: 30\nRecursive: O(2^n), Iterative: O(n)

Hints

Hint 1: The recursive version recomputes the same subproblems over and over. Draw the call tree for fib(5) — notice how fib(3) is computed twice, fib(2) three times.

Hint 2: Count the actual function calls. For n=30, the recursive version makes over 2 million calls. The iterative version does exactly 30 additions.

#9Append vs Insert(0) — The Hidden O(n)Medium

listappendinsertamortized-O(1)

Time list.append() vs list.insert(0, x) on 100,000 operations and explain the Big-O difference.

Python

import time

n = 100_000

# Benchmark append — O(1) amortized per operation
lst_append = []
start = time.perf_counter()
for i in range(n):
    lst_append.append(i)
append_time = time.perf_counter() - start

# Benchmark insert(0) — O(n) per operation
lst_insert = []
start = time.perf_counter()
for i in range(n):
    lst_insert.insert(0, i)
insert_time = time.perf_counter() - start

print(f"append ({n} ops): {append_time:.4f}s")
print(f"insert(0) ({n} ops): {insert_time:.4f}s")
print(f"insert(0) is {insert_time / max(append_time, 1e-9):.0f}x slower")
print(f"\nappend is O(1) amortized, insert(0) is O(n)")
print(f"Total: append = O(n) for n ops, insert(0) = O(n²) for n ops")

# Show the quadratic growth of insert(0)
print("\ninsert(0) time doubles roughly 4x with each 2x increase:")
for size in [10_000, 20_000, 40_000, 80_000]:
    test_list = []
    start = time.perf_counter()
    for i in range(size):
        test_list.insert(0, i)
    elapsed = time.perf_counter() - start
    print(f"  n={size:>6,}: {elapsed:.4f}s")

Solution

list.append(x) is O(1) amortized:

Python lists use a dynamic array internally. When you append, the element goes at the end. If the array is full, Python allocates a new array ~1.125x the old size and copies everything over. This resize happens rarely, so the average cost per append is O(1).

list.insert(0, x) is O(n):

Inserting at position 0 means every existing element must shift one position to the right to make room. For a list of 100,000 elements, that is 100,000 memory moves per insert. Over n inserts, the total is 1 + 2 + 3 + ... + n = O(n²).

Practical advice:

• Need a queue (FIFO)? Use collections.deque — it has O(1) appendleft() and popleft().
• Building a reversed list? Use append then reverse() at the end — O(n) total instead of O(n²).
• This is one of the most common hidden performance bugs in Python code.

Expected Output

append (100000 ops): ~fast\ninsert(0) (100000 ops): ~slow\nappend is O(1) amortized, insert(0) is O(n)

Hints

Hint 1: Think about what happens in memory when you insert at position 0. Every existing element must shift one position to the right.

Hint 2: list.append() is O(1) amortized because Python over-allocates the internal array. list.insert(0, x) is O(n) because all n elements must be moved.

---

Hard

#10Memoized Fibonacci — From O(2^n) to O(n)Hard

memoizationdynamic-programmingfibonaccioptimization

Implement memoized Fibonacci and measure the complexity improvement with call counters. Then compute fib(100) — something impossible with naive recursion.

Python

import time

# Naive recursive — O(2^n)
naive_calls = 0
def fib_naive(n):
    global naive_calls
    naive_calls += 1
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

# Memoized recursive — O(n)
memo_calls = 0
def fib_memo(n, memo=None):
    global memo_calls
    memo_calls += 1
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

# Compare call counts at n=30
naive_calls = 0
result_naive = fib_naive(30)
print(f"fib_naive(30): {naive_calls:,} calls, result={result_naive}")

memo_calls = 0
result_memo = fib_memo(30)
print(f"fib_memo(30):  {memo_calls} calls, result={result_memo}")

# Now do n=100 — impossible for naive
memo_calls = 0
result_100 = fib_memo(100)
print(f"fib_memo(100): {memo_calls} calls, result={result_100}")
print("(Naive recursion at n=100 would need ~10^29 calls — not feasible)")

# Show linear growth of memo calls
print("\nMemoized call counts (linear growth):")
for test_n in [10, 50, 100, 200, 500]:
    memo_calls = 0
    fib_memo(test_n)
    print(f"  n={test_n:>4}: {memo_calls:>5} calls  (roughly 2n)")

print("\nComplexity reduced from O(2^n) to O(n)")

Solution

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Why O(n):

Without memoization, fib(30) makes 2,692,537 calls because every subproblem is recomputed from scratch. With memoization:

1. fib(30) calls fib(29) and fib(28).
2. fib(29) calls fib(28) and fib(27). But wait — fib(28) was already computed and cached.
3. Every fib(k) is computed exactly once. After that, it is a O(1) dictionary lookup.

Total unique computations: n+1 (from fib(0) to fib(n)). Each does O(1) work. Total: O(n).

Call count is ~2n because each unique fib(k) is called once to compute it, and once more when a parent checks the cache. The exact count is 2n - 1 for n greater than 1.

Space complexity: O(n) for the memo dictionary + O(n) for the recursion call stack.

Production note: Python has a built-in decorator for this: @functools.lru_cache. It handles the memo dictionary automatically and adds features like max cache size.

Starter Code

def fib_memo(n, memo=None):
    """Fibonacci with memoization.
    Should be O(n) time, O(n) space.
    Track call count to prove it.
    """
    pass

Expected Output

fib_naive(30): 2692537 calls\nfib_memo(30): 59 calls\nfib_memo(100): 199 calls (impossible for naive!)\nComplexity reduced from O(2^n) to O(n)

Hints

Hint 1: Use a dictionary to cache previously computed results. Before computing fib(n), check if it is already in the cache. If yes, return it immediately. If no, compute it, store it, then return it.

Hint 2: With memoization, each fib(k) for k from 0 to n is computed exactly once. That is n+1 computations, each doing O(1) work (a dictionary lookup + an addition). Total: O(n).

#11O(n log n) vs O(n²) Sort ShowdownHard

sortingO(n-log-n)O(n²)comparison

Implement both bubble sort (O(n²)) and merge sort (O(n log n)) with comparison counters. Run them on the same data at different sizes and demonstrate the complexity difference empirically.

Python

import random
import time

def bubble_sort_counted(lst):
    """O(n²) sort with comparison counter."""
    arr = lst[:]
    comparisons = 0
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            comparisons += 1
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr, comparisons

def merge_sort_counted(lst):
    """O(n log n) sort with comparison counter."""
    counter = [0]  # Mutable container for recursive tracking

    def merge_sort_inner(arr):
        if len(arr) <= 1:
            return arr
        mid = len(arr) // 2
        left = merge_sort_inner(arr[:mid])
        right = merge_sort_inner(arr[mid:])
        return merge(left, right)

    def merge(left, right):
        result = []
        i = j = 0
        while i < len(left) and j < len(right):
            counter[0] += 1
            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

    sorted_arr = merge_sort_inner(lst)
    return sorted_arr, counter[0]

# Verify correctness
random.seed(42)
test = [random.randint(0, 1000) for _ in range(20)]
b_result, _ = bubble_sort_counted(test)
m_result, _ = merge_sort_counted(test)
assert b_result == m_result == sorted(test), "Sort implementations are incorrect!"
print("Both sorts produce correct results.\n")

# Compare at multiple sizes
print(f"{'n':>6} | {'Bubble comps':>14} | {'Merge comps':>12} | {'Ratio':>8} | {'Bubble time':>12} | {'Merge time':>12}")
print("-" * 80)

prev_bubble = prev_merge = None
for n in [500, 1000, 2000, 4000]:
    data = [random.randint(0, n * 10) for _ in range(n)]

    start = time.perf_counter()
    _, bubble_comps = bubble_sort_counted(data)
    bubble_time = time.perf_counter() - start

    start = time.perf_counter()
    _, merge_comps = merge_sort_counted(data)
    merge_time = time.perf_counter() - start

    ratio = bubble_comps / max(merge_comps, 1)
    print(f"{n:>6} | {bubble_comps:>14,} | {merge_comps:>12,} | {ratio:>7.1f}x | {bubble_time:>11.4f}s | {merge_time:>11.4f}s")

print("\nBubble sort: O(n²) — doubling n quadruples comparisons")
print("Merge sort: O(n log n) — doubling n slightly more than doubles comparisons")
print("The gap widens dramatically as n grows.")

Solution

def bubble_sort_counted(lst):
    arr = lst[:]
    comparisons = 0
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            comparisons += 1
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr, comparisons

def merge_sort_counted(lst):
    counter = [0]

    def merge_sort_inner(arr):
        if len(arr) <= 1:
            return arr
        mid = len(arr) // 2
        left = merge_sort_inner(arr[:mid])
        right = merge_sort_inner(arr[mid:])
        return merge(left, right)

    def merge(left, right):
        result = []
        i = j = 0
        while i < len(left) and j < len(right):
            counter[0] += 1
            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

    sorted_arr = merge_sort_inner(lst)
    return sorted_arr, counter[0]

Bubble sort — O(n²):

• Two nested loops. The outer loop runs n times, the inner loop runs up to n-1 times.
• Exact comparisons: n(n-1)/2. For n=4000, that is about 8,000,000.
• Doubling n quadruples the comparisons: 500 to 1000 means 4x more work.

Merge sort — O(n log n):

• Divides the array in half (log n levels), merges at each level (n comparisons per level).
• For n=4000, that is about 4000 * 12 = ~48,000 comparisons.
• Doubling n slightly more than doubles the comparisons (because log n grows slowly).

Why O(n log n) cannot be beaten for comparison-based sorting: This is a proven lower bound. Any algorithm that sorts by comparing elements must make at least O(n log n) comparisons in the worst case. Merge sort achieves this bound. Bubble sort does not.

Python's built-in sorted() uses Timsort — a hybrid merge sort + insertion sort that is O(n log n) worst case but adapts to partially sorted data for better real-world performance.

Starter Code

def bubble_sort(lst):
    """O(n²) sort — implement and count comparisons."""
    pass

def merge_sort(lst):
    """O(n log n) sort — implement and count comparisons."""
    pass

Expected Output

n=1000:  bubble=~500000 comps, merge=~10000 comps\nn=5000:  bubble grows 25x, merge grows ~5.5x\nBubble is O(n²), Merge is O(n log n)

Hints

Hint 1: Bubble sort: nested loops, compare adjacent elements, swap if out of order. Count every comparison. Merge sort: split in half, recursively sort each half, merge by comparing elements.

Hint 2: Use a mutable counter (a list with one integer element) passed through recursive calls to track comparisons in merge sort. Returning comparison counts through return values also works.

#12Build a Complexity AnalyzerHard

empirical-analysiscurve-fittingcomplexity-verification

Build a function that empirically determines the Big-O class of any given function by running it at multiple input sizes and analyzing the growth rate.

Python

import time

def analyze_complexity(func, sizes, setup_func=None, num_trials=3):
    """Empirically determine the Big-O class of a function."""
    if setup_func is None:
        setup_func = lambda n: list(range(n))

    times = []
    for n in sizes:
        data = setup_func(n)
        best = float('inf')
        for _ in range(num_trials):
            start = time.perf_counter()
            func(data)
            elapsed = time.perf_counter() - start
            best = min(best, elapsed)
        times.append(best)

    # Compute growth ratios between consecutive sizes
    ratios = []
    size_ratios = []
    for i in range(1, len(sizes)):
        if times[i - 1] > 1e-9:
            ratios.append(times[i] / times[i - 1])
            size_ratios.append(sizes[i] / sizes[i - 1])

    # Classify based on average ratio
    if not ratios:
        return "unknown"

    avg_ratio = sum(ratios) / len(ratios)
    avg_size_ratio = sum(size_ratios) / len(size_ratios)

    # Expected ratios when doubling n:
    # O(1):      ratio ~ 1.0
    # O(log n):  ratio ~ 1.0-1.3  (slightly above 1)
    # O(n):      ratio ~ 2.0
    # O(n log n): ratio ~ 2.0-2.5
    # O(n²):     ratio ~ 4.0
    # O(n³):     ratio ~ 8.0

    if avg_ratio < 1.3:
        # Could be O(1) or O(log n) — check if time grows at all
        if times[-1] < times[0] * 1.5 and times[-1] < 1e-5:
            complexity = "O(1)"
        else:
            complexity = "O(log n)"
    elif avg_ratio < 2.5:
        complexity = "O(n)"
    elif avg_ratio < 3.5:
        complexity = "O(n log n)"
    elif avg_ratio < 6.0:
        complexity = "O(n²)"
    else:
        complexity = "O(n³) or worse"

    return {
        "complexity": complexity,
        "sizes": sizes,
        "times": [f"{t:.6f}s" for t in times],
        "ratios": [f"{r:.2f}" for r in ratios],
    }


# --- Test functions with known complexities ---

def linear_scan(data):
    total = 0
    for x in data:
        total += x
    return total

def quadratic_pairs(data):
    count = 0
    n = len(data)
    for i in range(n):
        for j in range(i + 1, n):
            count += 1
    return count

def binary_search_test(data):
    target = data[-1]
    low, high = 0, len(data) - 1
    while low <= high:
        mid = (low + high) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

def constant_lookup(data):
    return data[0] + data[-1]


# Analyze each function
print("=" * 60)
print("EMPIRICAL COMPLEXITY ANALYSIS")
print("=" * 60)

# Linear: test with larger sizes
result = analyze_complexity(linear_scan, [10000, 20000, 40000, 80000, 160000])
print(f"\nlinear_scan: {result['complexity']}")
print(f"  Sizes:  {result['sizes']}")
print(f"  Times:  {result['times']}")
print(f"  Ratios: {result['ratios']} (expect ~2.0 for O(n))")

# Quadratic: use smaller sizes (it is slow)
result = analyze_complexity(quadratic_pairs, [500, 1000, 2000, 4000])
print(f"\nquadratic_pairs: {result['complexity']}")
print(f"  Sizes:  {result['sizes']}")
print(f"  Times:  {result['times']}")
print(f"  Ratios: {result['ratios']} (expect ~4.0 for O(n²))")

# Log n: needs sorted data
result = analyze_complexity(binary_search_test, [10000, 20000, 40000, 80000, 160000])
print(f"\nbinary_search_test: {result['complexity']}")
print(f"  Sizes:  {result['sizes']}")
print(f"  Times:  {result['times']}")
print(f"  Ratios: {result['ratios']} (expect ~1.0 for O(log n))")

# O(1): constant
result = analyze_complexity(constant_lookup, [10000, 20000, 40000, 80000, 160000])
print(f"\nconstant_lookup: {result['complexity']}")
print(f"  Sizes:  {result['sizes']}")
print(f"  Times:  {result['times']}")
print(f"  Ratios: {result['ratios']} (expect ~1.0 for O(1))")

print("\n" + "=" * 60)
print("All complexities verified empirically!")

Solution

import time

def analyze_complexity(func, sizes, setup_func=None, num_trials=3):
    if setup_func is None:
        setup_func = lambda n: list(range(n))

    times = []
    for n in sizes:
        data = setup_func(n)
        best = float('inf')
        for _ in range(num_trials):
            start = time.perf_counter()
            func(data)
            elapsed = time.perf_counter() - start
            best = min(best, elapsed)
        times.append(best)

    ratios = []
    size_ratios = []
    for i in range(1, len(sizes)):
        if times[i - 1] > 1e-9:
            ratios.append(times[i] / times[i - 1])
            size_ratios.append(sizes[i] / sizes[i - 1])

    avg_ratio = sum(ratios) / len(ratios) if ratios else 0

    if avg_ratio < 1.3:
        if times[-1] < times[0] * 1.5 and times[-1] < 1e-5:
            complexity = "O(1)"
        else:
            complexity = "O(log n)"
    elif avg_ratio < 2.5:
        complexity = "O(n)"
    elif avg_ratio < 3.5:
        complexity = "O(n log n)"
    elif avg_ratio < 6.0:
        complexity = "O(n²)"
    else:
        complexity = "O(n³) or worse"

    return {
        "complexity": complexity,
        "sizes": sizes,
        "times": [f"{t:.6f}s" for t in times],
        "ratios": [f"{r:.2f}" for r in ratios],
    }

How the analyzer works:

The key insight is the doubling test. When you double the input size and measure how the runtime changes:

O(1):       ratio = 1.0    (no change)
O(log n):   ratio = 1.05   (barely changes)
O(n):       ratio = 2.0    (doubles)
O(n log n): ratio = 2.1    (slightly more than doubles)
O(n²):      ratio = 4.0    (quadruples)
O(n³):      ratio = 8.0    (octuples)
O(2^n):     ratio = 2^n    (explodes)

Why use min of multiple trials: Timer noise from OS scheduling and other processes can skew results. Taking the minimum of several runs gives the best estimate of the true computation time — the minimum is least affected by external interference.

Limitations:

• Very fast functions (under microseconds) are hard to measure reliably.
• Cache effects can distort results at certain sizes.
• Amortized complexities (like dynamic array resizing) need many operations to average out.
• This approach classifies complexity empirically — it does not prove it mathematically. A rigorous proof requires analyzing the algorithm's structure.

Production use case: This technique is used in competitive programming to verify that your solution will pass within time limits, and in performance engineering to detect unexpected complexity regressions in codebases.

Starter Code

def analyze_complexity(func, sizes, setup_func=None):
    """Run func at different input sizes and determine its Big-O class.
    
    Args:
        func: function that takes a single argument (the input)
        sizes: list of input sizes to test
        setup_func: creates input of given size (default: range(n))
    
    Returns:
        dict with sizes, times, and estimated complexity class
    """
    pass

Expected Output

linear_scan: O(n)\nquadratic_pairs: O(n²)\nbinary_search_test: O(log n)\nconstant_lookup: O(1)

Hints

Hint 1: Measure the execution time at several input sizes. Then compute the ratio of times: if doubling the input doubles the time, it is O(n). If it quadruples the time, it is O(n²). If it barely changes, it is O(1) or O(log n).

Hint 2: To distinguish O(1) from O(log n), check if the time increases at all. For O(log n), the ratio should be close to 1 + log(2)/log(n). For O(1), the ratio should be very close to 1.0.