Worked Example 1: The Load Balancer

A load balancer sits in front of a pool of servers. For every incoming request, it must choose which server to send it to. The choice matters: an unbalanced distribution creates hotspots (FM6); a distribution that ignores server health wastes capacity.

Find the bottleneck: the routing decision — made millions of times per second.

Identify the data structure: the server pool. A list of N servers, each with state (current load, health).

Identify the algorithm: key-to-server mapping. There are several options: - Round robin: iterate the list, assign each request to the next server. O(1) per decision. - Least connections: find the server with fewest active connections. O(N) per decision if naive, O(log N) with a min-heap. - Hash-based: hash the request key (source IP, session ID) to a server index. O(1) per decision, sticky routing.

Name the complexity: O(1) for round-robin and hash-based; O(log N) for heap-based least connections.

What does this tell you? A round-robin balancer will not degrade as the server pool grows. A naive least-connections balancer will. If your load balancer starts showing elevated routing latency at 100 servers that it did not show at 10 servers, the cause is identifiable — and the implementation detail to investigate becomes clear.

# Round-robin: O(1) per call, ignores server state
class RoundRobinBalancer:
    def __init__(self, servers: list[str]):
        self.servers = servers
        self.index = 0

    def next_server(self) -> str:
        server = self.servers[self.index % len(self.servers)]
        self.index += 1
        return server

# Least-connections: O(log N) per call, uses a min-heap on connection count
import heapq

class LeastConnectionsBalancer:
    def __init__(self, servers: list[str]):
        # heap entries: (connection_count, server_name)
        self.heap = [(0, s) for s in servers]
        heapq.heapify(self.heap)

    def acquire(self) -> str:
        count, server = heapq.heappop(self.heap)
        heapq.heappush(self.heap, (count + 1, server))
        return server

The round-robin balancer is O(1). The heap-based balancer is O(log N). This matters when N is large and routing decisions are on the critical path of every request.

Worked Example 2: The Session Cache

A session cache stores user session data — authentication tokens, preferences, temporary state. The system is a cache layer in front of a database. Its job: make reads fast by avoiding a database round-trip for recently accessed data.

Find the bottleneck: the lookup operation. Every authenticated request requires a session lookup.

Identify the data structure: a key-value map. Session ID → session data.

Identify the algorithm: hash-based lookup. The session ID is the key; the hash map makes lookup O(1).

Name the complexity: O(1) average for lookup, O(N) for full scan (which a session cache should never need to do).

What does this tell you? Session cache latency should be flat regardless of how many sessions are stored. If you observe cache latency increasing with session count, the cache is not using O(1) lookup — something is wrong. This becomes diagnosable once the algorithm under investigation is identified.

# O(1) lookup — this is the invariant the session cache must preserve
class SessionCache:
    def __init__(self):
        self._store: dict[str, dict] = {}

    def get(self, session_id: str) -> dict | None:
        return self._store.get(session_id)  # O(1) average

    def set(self, session_id: str, data: dict) -> None:
        self._store[session_id] = data       # O(1) average

    def delete(self, session_id: str) -> None:
        self._store.pop(session_id, None)    # O(1) average

Worked Example 3: The Dependency Resolver

A package manager (pip, npm, maven) must determine which packages to install and in what order. Package A depends on B and C. B depends on D. The installer must ensure D is installed before B, and B before A.

Find the bottleneck: determining installation order at resolve time.

Identify the data structure: a directed acyclic graph (DAG). Packages are nodes; “depends on” relationships are directed edges.

Identify the algorithm: topological sort. Return an ordering where every dependency comes before the thing that depends on it.

Name the complexity: O(V + E) where V is the number of packages and E is the number of dependency edges. Linear in the size of the dependency graph.

What does this tell you? Dependency resolution time should scale linearly with the number of packages and dependencies. If a package manager is slow, the cause is almost never the topological sort itself (O(V+E) is fast) — it is the graph construction phase: downloading package metadata, resolving version constraints, building the edges. Understanding the algorithm tells you where to look.

from collections import defaultdict, deque

def topological_sort(packages: list[str], dependencies: dict[str, list[str]]) -> list[str]:
    """
    Returns install order: every dependency appears before the package that requires it.
    Uses Kahn's algorithm: BFS on nodes with in-degree 0.
    """
    in_degree = defaultdict(int)
    graph = defaultdict(list)

    for pkg, deps in dependencies.items():
        for dep in deps:
            graph[dep].append(pkg)
            in_degree[pkg] += 1

    # Start with packages that have no dependencies
    queue = deque([p for p in packages if in_degree[p] == 0])
    order = []

    while queue:
        pkg = queue.popleft()
        order.append(pkg)
        for dependent in graph[pkg]:
            in_degree[dependent] -= 1
            if in_degree[dependent] == 0:
                queue.append(dependent)

    if len(order) != len(packages):
        raise ValueError("Circular dependency detected")
    return order

The General Method

The three worked examples follow the same four-step method. Apply it to any system:

The O-notation is the answer to “how will this system behave at 10× scale?” Every performance conversation that proceeds without naming the complexity is guessing.