Cairn
guides · reference tool, not a category comparison

↩ back to Guides

Complexity Cheat Sheet

Why this exists

Every algorithm and data structure page on this site states its own time (and usually space) complexity in the small header line right under the nav — but comparing two of them has always meant opening both pages. Every one of Cairn's 345 algorithms and data structures states its own complexity in that line, and this page collects all of them into one table: sortable by name, type, category, or complexity, and filterable by any of those at once. Nothing here is re-derived or rounded — each row's complexity cell is the literal text from that page's own header, copied by a script, not reasoned about fresh. If a page's own claim is ever wrong, the fix belongs on that page, and this table will pick it up the next time it's regenerated.

The table

Name Type Category Complexity, as stated on its own page

Reading it well

Three things this table can't do for you. First, sorting the Complexity column is a plain text sort on each row's literal words, not a true sort by asymptotic growth — it groups rows that happen to start with the same characters ("O(1)" entries cluster together, "O(n" entries cluster together), not rows that actually grow at the same rate past some threshold, and it has no way to rank O(n) against O(log n) correctly if either is phrased with a qualifier first. Sort by Category or Type instead if you want a meaningful grouping; use the filter box to pull out a specific class (typing log n finds everything whose own page mentions it).

Second, a lot of these cells carry a qualifier for a reason — "amortized," "average," "worst case," "expected" — and the qualifier is not decoration. Two rows that both say O(log n) can still mean a guarantee on every single operation versus a guarantee only once the cost is spread over many; see Amortized Analysis for what that distinction actually buys you, and read past the first few characters of a cell before treating two matching-looking entries as equivalent.

Third, and the one this site keeps coming back to: two entries in the same Big-O class can still run at very different real speeds, because Big-O hides constant factors on purpose. How Fast Is Big-O, Really? turns the common classes into real operation counts and wall-clock numbers; Same Big-O, Different Speed is built entirely around pairs that share a row here and disagree anyway. This table is a map, not the territory — use it to find candidates, then open the page for the real argument.

Guides themselves aren't rows here — a comparison essay doesn't have one complexity of its own to state, which is exactly why this table only pulls from algorithms/ and data-structures/ pages.