01 — Time/Space Complexity & Dynamic Arrays

At a glance

After completing this lesson you can:

• Accurately evaluate Big-O asymptotic time and auxiliary space complexity in Python backend workflows.
• Explain CPython dynamic array over-allocation mechanics (list.append amortized $O(1)$ vs list concatenation/slicing $O(n)$).
• Spot and refactor unintentional $O(n^2)$ memory copying operations in high-throughput payload handling.

Time: ~50 minutes · Prerequisites: Phase 0 Complete

Reading Companion

• Book: Grokking Algorithms (2nd Edition) — Aditya Y. Bhargava
• Chapter 1: Introduction to Algorithms (Binary Search, Big-O notation, Algorithm speed).
• Chapter 2: Selection Sort (Arrays and Linked Lists, Memory allocation).
• Book: Fluent Python (2nd Edition) — Luciano Ramalho
• Chapter 2: An Array of Sequences (List comprehensions, Memory views, Array mechanics).

Why this matters in production

In production, an algorithm running at $O(n)$ handles a surge of 100,000 incoming webhooks in 20 milliseconds. An algorithm running at $O(n^2)$—often introduced innocently via repeated list.insert(0, ...) or string/list additions inside loops—will freeze CPU cores for 45 minutes, triggering gateway timeouts (HTTP 504) and cascading service failures across the fleet.

Deep dive

1. Big-O: Asymptotic Analysis for Production

Big-O measures how resource consumption (time or memory) scales as input size $n$ approaches infinity:

• $O(1)$ Constant: Dictionary key lookup, array indexing by index.
• $O(\log n)$ Logarithmic: Binary search over sorted data.
• $O(n)$ Linear: Single pass scan, counting elements, list.copy().
• $O(n \log n)$ Linearithmic: Timsort (Python's built-in sorted() / .sort()).
• $O(n^2)$ Quadratic: Nested loops over the same collection; repeated list.insert(0, ...) inside a loop.

2. CPython Dynamic Arrays (list) Under the Hood

In CPython, a list is not a linked list; it is a contiguous array of pointer references (PyObject**).

• When capacity is full, list.append() over-allocates proportional extra space (new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6)).
• Because resizes happen logarithmically less frequently as size grows, append is amortized $O(1)$.
• But inserting or popping at index 0 forces every single pointer to shift right or left by 1 position: an expensive $O(n)$ memory move!

CPython list resize pattern:
Size 0 -> Allocated 0
Append 1 -> Allocates 4 slots [p0, _, _, _]
Append 2, 3, 4 -> Fills existing slots (O(1))
Append 5 -> Reallocates to 8 slots [p0..p4, _, _, _] (copies pointers)

Hands on

python3 phase1-cs-and-architecture/01-data-structures/01-complexity-and-arrays/examples/01_demo.py
python3 phase1-cs-and-architecture/01-data-structures/01-complexity-and-arrays/examples/02_trap.py

AI Trap & Code Review

# BAD AI-GENERATED CODE — UNINTENTIONAL O(n^2) PAYLOAD ASSEMBLY
def prepend_audit_logs(events: list[dict], new_events: list[dict]) -> list[dict]:
    result = []
    for ev in events:
        result.append(ev)
    for new_ev in new_events:
        result.insert(0, new_ev)  # O(n) shift on EVERY insertion -> O(n*m) runtime!
    return result

Exercises

1. Rung 1 (estimate_growth_category): Classify runtime scaling ratios into "O(1)", "O(log n)", "O(n)", "O(n log n)", or "O(n^2)" given baseline and scaled timing measurements.
2. Rung 2 (collect_events_fifo — Fix the AI Bug): Fix an $O(n^2)$ FIFO collector that uses list.insert(0, item) by refactoring it to linear $O(n)$ execution time.
3. Rung 3 (amortized_capacity_tracker): Simulate CPython's list append growth curve: given a sequence of append operations, record every reallocation step (old capacity, new capacity, copied element count).
4. Rung 4 (merge_sorted_intervals): Implement $O(n \log n)$ interval merging for overlapping time ranges [(start_1, end_1), ...].
5. Rung 5 (bounded_fast_buffer): Build an in-memory fixed-capacity append buffer that drops the oldest items when exceeding max_size in strict $O(1)$ amortized time per append and index lookup.

Wrapping up

Can you explain?

1. Why is list.append amortized $O(1)$ whereas list.insert(0, val) is strictly $O(n)$?
2. What is the difference between time complexity and auxiliary space complexity?
3. Why does slicing a list (items[:k]) allocate new memory in Python?

Further Reading & References

• CPython Source: listobject.c (Dynamic Array Implementation)
• Raymond Hettinger: Modern Dictionaries by Key-Sharing
• Alex Xu: System Design Interview — Rate Limiter Design
• Tim Roughgarden: Algorithms Illuminated Series