Algorithmic Complexity and Big-O

Updated

October 31, 2026

Algorithmic Complexity and Big-O

Algorithmic complexity describes how execution time and memory consumption scale as the volume of input data increases. The boring default in Python is to write concise list comprehensions and dictionary lookups until profiling reveals a bottleneck. However, understanding Big-O notation (\(O(1)\), \(O(\log n)\), \(O(n)\), \(O(n \log n)\), \(O(n^2)\)) protects your services from catastrophic slowdowns when desk ticket volumes grow from 100 rows to 1,000,000 rows.

Mental model

Big-O measures the growth rate in the worst-case scenario, ignoring CPU frequency and minor constant factors. An algorithm with quadratic complexity \(O(n^2)\) will eventually run thousands of times slower than an \(O(n \log n)\) algorithm on the same hardware once \(n\) grows large enough.

Execution Time
  ^
  |                                                O(n^2) Quadratic
  |                                               /
  |                                 O(n log n)   /
  |                                /            /
  |                     O(n) Linear            /
  |                    /                      /
  |       O(log n)    /                      /
  |      /           /                      /
  |-----/-----------/----------------------/-----------------> Input Size (n)
  |  O(1) Constant Time
  +-----------------------------------------------------------

Core time complexity classes in Python:

Complexity	Common Name	Python Example	Scaling Behavior (\(n = 100{,}000\))
\(O(1)\)	Constant	`dict` lookup `d[key]`, `list.append()`	Instantaneous (~50 ns)
\(O(\log n)\)	Logarithmic	Binary search using `bisect`	~17 operations
\(O(n)\)	Linear	Linear search `target in my_list`, `min()`, `max()`	100,000 steps (~2 ms)
\(O(n \log n)\)	Linearithmic	Python’s Timsort `my_list.sort()`	~1.7 million steps (~30 ms)
\(O(n^2)\)	Quadratic	Nested loop comparing every item to every other item	10,000,000,000 steps (~25 seconds)

Space complexity follows the identical asymptotic curve: creating a new list of size \(n\) takes \(O(n)\) auxiliary memory, while modifying data in-place takes \(O(1)\) extra space.

Worked examples

Case 1: Dict lookup O(1) vs List linear search O(n)

Save as complexity_lookup.py. Compare looking up desk orders using an \(O(1)\) dictionary hash table versus an \(O(n)\) list scan.

# complexity_lookup.py
import time
from dataclasses import dataclass


@dataclass(slots=True)
class Ticket:
    id: int
    table: int
    status: str


def find_in_list(tickets: list[Ticket], target_id: int) -> Ticket | None:
    for t in tickets:
        if t.id == target_id:
            return t
    return None


def main() -> None:
    count = 100_000
    tickets = [
        Ticket(id=1000 + i, table=(i % 20) + 1, status="open")
        for i in range(count)
    ]
    ticket_map = {t.id: t for t in tickets}

    # Search for the last element (worst case for linear scan)
    target = 1000 + count - 1

    # Measure list linear scan O(n)
    start_time = time.perf_counter()
    found_list = find_in_list(tickets, target)
    list_duration = (time.perf_counter() - start_time) * 1000

    # Measure dict hash lookup O(1)
    start_time = time.perf_counter()
    found_dict = ticket_map.get(target)
    dict_duration = (time.perf_counter() - start_time) * 1000

    assert found_list is not None and found_dict is not None
    print(f"List search O(n): found ID={found_list.id} in {list_duration:.4f} ms")
    print(f"Dict lookup O(1): found ID={found_dict.id} in {dict_duration:.4f} ms")


if __name__ == "__main__":
    main()

Run:

uv run python complexity_lookup.py

Output:

List search O(n): found ID=100999 in 1.4820 ms
Dict lookup O(1): found ID=100999 in 0.0004 ms

Case 2: Detecting duplicates (Quadratic nested loops vs Linear Set)

Save as complexity_duplicates.py. Show the performance collapse of \(O(n^2)\) duplicate checking compared to an \(O(n)\) set lookup.

# complexity_duplicates.py
import time


def has_duplicates_quadratic(ids: list[int]) -> bool:
    n = len(ids)
    for i in range(n):
        for j in range(i + 1, n):
            if ids[i] == ids[j]:
                return True
    return False


def has_duplicates_linear(ids: list[int]) -> bool:
    seen: set[int] = set()
    for item in ids:
        if item in seen:
            return True
        seen.add(item)
    return False


def main() -> None:
    n = 10_000
    order_ids = [i * 2 for i in range(n)]  # all unique numbers

    t0 = time.perf_counter()
    quad_result = has_duplicates_quadratic(order_ids)
    quad_time = (time.perf_counter() - t0) * 1000

    t1 = time.perf_counter()
    linear_result = has_duplicates_linear(order_ids)
    linear_time = (time.perf_counter() - t1) * 1000

    print(f"Quadratic O(n^2): duplicate={quad_result} in {quad_time:.2f} ms")
    print(f"Linear O(n):    duplicate={linear_result} in {linear_time:.2f} ms")


if __name__ == "__main__":
    main()

Run:

uv run python complexity_duplicates.py

Output:

Quadratic O(n^2): duplicate=False in 1215.30 ms
Linear O(n):    duplicate=False in 0.42 ms

The trap

The hidden quadratic trap in Python is repeated string concatenation inside a loop (text += chunk) or inserting at the head of a standard list (my_list.insert(0, item)).

In Python, inserting at index 0 shifts every subsequent element one pointer down in memory, converting an \(n\)-item loop into an \(O(n^2)\) memory copier. For FIFO queues, always use collections.deque, which provides true \(O(1)\) appends and pops on both ends.

# bad_queue_trap.py
import time
from collections import deque


def main() -> None:
    n = 40_000

    # TRAP: list.insert(0, x) shifts all n elements on every step -> O(n^2)
    t0 = time.perf_counter()
    bad_list: list[int] = []
    for i in range(n):
        bad_list.insert(0, i)
    bad_duration = time.perf_counter() - t0

    # BORING DEFAULT: deque.appendleft(x) -> O(1) per step -> O(n) total
    t1 = time.perf_counter()
    good_deque: deque[int] = deque()
    for i in range(n):
        good_deque.appendleft(i)
    good_duration = time.perf_counter() - t1

    print(f"list.insert(0, x) O(n^2): {bad_duration:.4f} seconds")
    print(f"deque.appendleft(x) O(n): {good_duration:.4f} seconds")


if __name__ == "__main__":
    main()

Run:

uv run python bad_queue_trap.py

Output:

list.insert(0, x) O(n^2): 0.1850 seconds
deque.appendleft(x) O(n): 0.0021 seconds

The boring rule

Use standard dict or set when checking membership across large datasets (\(n > 100\)). A target in my_list scan is linear and slow.
Never call my_list.insert(0, x) or my_list.pop(0) in high-throughput pipelines. Use collections.deque instead.
Preallocate or use list comprehensions ([f(x) for x in seq]) rather than repeatedly building lists with .insert() or .extend() inside nested loops.
For string building, use "".join(chunks) rather than repeatedly concatenating with +=.

Try this

Benchmark target in my_set vs target in my_list across collection sizes \(n = 100, 1000, 10000\) using time.perf_counter().
Write a function that finds if two lists share any common elements in \(O(n + m)\) time instead of \(O(n \times m)\) nested loops.