A service models a social graph of a hundred thousand users, each with about eight connections, and someone proposes a `boolean[][]` adjacency matrix because "it's the simplest representation and edge lookup is O(1)." Walk through what that decision actually costs, and what you'd build instead.

A hundred thousand users squared is ten billion cells, and even at the theoretical best of one bit per cell that's roughly 1.2 GB — but Java has no way to store a boolean in less than a full byte, so a real boolean[][] costs closer to ten gigabytes, which will not fit in a typical service's heap at all. The graph itself is tiny by comparison: eight connections each is 400,000 directed-edge entries (each undirected friendship stored twice), which as an adjacency list — a Map from each user to a list of their friends — costs around 19 MB. The reason the matrix looks appealing is that it makes "is A connected to B" a single O(1) array read, but that question is being asked for every one of ten billion possible pairs whether or not the friendship could plausibly exist, and this graph uses only eight thousandths of one percent of those possible pairs — nearly all of the matrix is wasted space reserved for edges that will never exist. The adjacency list answers the same question in O(degree) — walking one user's short friend list — which for eight friends is effectively instant, at a fraction of a percent of the memory.