Overview
A reference table and quiz for algorithm complexity: eleven rows covering arrays, hash tables, balanced BSTs, heaps, the classic sorting algorithms, and graph traversal, each with best, average, and worst case plus space complexity and a one-line explanation of what drives the numbers. A quiz mode tests you on average-case complexity.
How It Works
In table mode, search across structure names, operations, and reasoning notes, and filter by category — Data structures, Sorting, or Graphs. Switch to Quiz mode and the tool asks for the average-case time complexity of a randomly drawn row, offering four multiple-choice options; after you answer, the reasoning note explains the result. Your wins, attempts, and accuracy percentage persist across visits, with a reset button in the sidebar.
Step-by-Step Usage Guide
- Browse or search the matrix for the structure or algorithm you are reviewing.
- Read the worst-case column and the reasoning note together — the note explains when the worst case bites.
- Switch to Quiz mode and answer average-case questions.
- Check your accuracy tile and reset the stats when you want a clean slate.
Technical Specifications & Standards
The matrix itself is deliberately conservative and matches the canonical treatments: hash-table lookup is listed as O(1) average but O(n) worst case because colliding keys can concentrate in one bucket; quicksort shows O(n log n) average against O(n²) worst case from unbalanced pivots; heapsort is flagged as the in-place O(1)-extra-space sort; and Dijkstra with a binary heap carries its O((V + E) log V) bound with the non-negative-weights assumption stated in the note. The quiz draws four options — the correct average case plus distractors — shuffled each round, and grades strictly against the average-case column. The underlying data is static and ships with the page, so the table works offline and costs no requests. Two limitations: eleven rows is a study aid, not an exhaustive reference (no red-black tree specifics, no amortised analysis of dynamic arrays), and the quiz stats — stored under the localStorage key CruxDev-big-o-matrix-v1 — measure drills, not understanding; the page itself notes the matrix is not a substitute for measuring real workloads.
Targeted Use Cases
- Revising for interviews by drilling the difference between average and worst case.
- Deciding between a hash table and a balanced BST for a lookup-heavy workload.
- Choosing a sort when worst-case guarantees or in-place constraints matter.
- Quickly confirming a complexity claim during a design discussion.
Notes & Gotchas
- Learn the reasoning notes, not just the letter grades — interviewers ask for the why.
- Use category filters to drill one family at a time before mixing them.
- Remember average-case entries assume typical inputs; adversarial input can hit the worst case.
- Treat the quiz accuracy as a progress signal, with resets to re-drill from zero.
Frequently Asked Questions
Which data structures and algorithms are covered?
Eleven rows: arrays (access, search, front-insert), hash tables, balanced BSTs, binary heaps, merge sort, quicksort, heapsort, breadth-first traversal, and Dijkstra with a min-heap. Each row includes best, average, worst, and space complexity plus a reasoning note.
Why is hash table lookup O(n) in the worst case?
When many keys collide into the same bucket, a lookup must scan them all. Good hash functions spread keys out, which is why O(1) average holds in practice — the table's note states exactly this assumption.
Does the quiz save my score?
Yes. Wins, attempts, and accuracy persist in localStorage under CruxDev-big-o-matrix-v1 and survive refreshes. The sidebar has a reset button, and clearing site data erases the stats.
Is this a complete complexity reference?
No. It is a curated study set covering the cases that come up in interviews and code reviews. It excludes amortised analysis, average-case nuances for specialised structures, and anything beyond the eleven core rows.