Big-O Algorithmic Time & Space Complexity Markdown Table Template
A complexity table is a compressed answer to “how does this get slower as the input grows?”. Candidates use it to revise for interviews, but it earns its keep in design reviews and library documentation, where a reviewer needs to see at a glance that a deduplication step is quadratic or that a lookup degrades under adversarial keys. Each row should describe one operation on one structure, or one algorithm, under stated assumptions.
Edit This Template
Edit cells, add rows, or sort — the Markdown updates livePaste cells from Excel or Google Sheets into the first header to replace the table · Tab / Enter / arrows move · Shift+F10 opens row & column actions
When to Use This Table
The three time columns are only meaningful with their assumptions attached. Average time for a hash table assumes a decent hash function and a bounded load factor; average time for quicksort assumes random input or a randomised pivot. Worst time is the guarantee you get against hostile input, which matters for anything exposed to the internet — hash-flooding attacks exist precisely because the worst case is O(n). Amortised bounds are a third thing again: a dynamic array append is O(1) amortised across a sequence of operations, while a single append can take O(n).
Space needs the same care. Some rows report total storage (an array of n elements is O(n)), others report auxiliary memory beyond the input (in-place quicksort needs only its recursion stack). Say which convention the column uses, define n and any other variables such as V and E above the table, and specify the variant — a balanced and an unbalanced binary search tree have different worst cases.
Formatting This Table in Markdown
A big-o algorithmic time & space complexity table puts a few things in cells that Markdown treats as syntax. These are the ones to watch so it renders correctly on GitHub, GitLab, Obsidian and docs sites.
Superscripts: use Unicode inside code spans
Inside backticks,
O(n<sup>2</sup>)andO(n^2)print the tag and caret literally, so writeO(n²)orO(2ⁿ)with Unicode superscripts. Outside backticks<sup>renders on GitHub and$O(n^2)$renders where math is supported; Unicode has no superscript for arbitrary letters, so something like n to the power k needs math (see math in tables).No spanning headers: repeat the group in each header
GFM has no colspan, so a single “Time” header cannot sit over three columns; names like
Best TimeandWorst Spacecarry the group in each header instead. If you want a spanning header, split time and space into two tables or switch that table to HTML.Flag slow worst cases with bold or a symbol, not colour
GitHub strips
styleattributes and<font>, so red quadratic cells are not possible. Bold the entries you want noticed, or add a marker such as ⚠️, and keep the notation in the cell so it still reads as text.Footnote markers: use † and leave a blank line
A line placed directly under a table becomes another row, so leave a blank line before a note such as “† amortized”. Prefer † or
<sup>1</sup>over a bare*marker: a note line that starts with*becomes a bullet, and two bare asterisks in one cell or paragraph can italicize the text between them.
What Goes in Each Column
| Column | Alignment | What to put here |
|---|---|---|
| Data Structure / Algorithm | left :--- | Name the structure or algorithm plus the operation and the variant: “Hash table (chaining) — lookup”, “Red-black tree — insert”, “Quicksort (random pivot)”. Left-aligned. Without the variant, the worst-case column cannot be correct. |
| Best Time | center :---: | Often the least informative column; include it where it is meaningful, such as insertion sort’s O(n) on already-sorted input. Code-formatted and centered. Do not use the best case to argue that an algorithm is fast. |
| Average Time | center :---: | Expected cost under a stated input model (random permutation, uniform hashing). Format as O(n log n) in backticks. If the bound is amortised rather than averaged over inputs, write O(1)* and explain the asterisk in a note. |
| Worst Time | center :---: | The bound that holds for every input of size n, which is what latency budgets and security reviews care about. Balanced trees exist to make this O(log n); if your row shows O(n) here, check you have not described the unbalanced case. |
| Worst Space | center :---: | Peak memory as a function of n, labelled as either total or auxiliary. Quicksort’s O(log n) holds only when the implementation recurses into the smaller partition first; naive recursion can use O(n) stack on bad input. |
How to Fill It In
- 1Write a one-line note above the table defining every variable (n = number of elements; V, E = vertices and edges) and whether space means total or auxiliary.
- 2Take each bound from a primary source: a standard algorithms textbook, the language’s own documentation (Python’s TimeComplexity wiki page, the Java Collections Javadoc), or the library source. Interview cheat sheets copy each other’s errors.
- 3Split multi-operation entries into separate rows. A heap’s
O(1)find-min andO(log n)insert in one row will be misread. - 4Sanity-check any bound you doubt with a doubling experiment: time the operation at n, 2n, and 4n. Linear code roughly doubles, quadratic code roughly quadruples, and
O(n log n)grows slightly faster than double. - 5Format every bound identically — all backticks, or all math — and escape vertical bars in notations such as
\|V\|so they do not split cells.
Ready-to-Paste Variations
Comparison sorts with stability and auxiliary space
The sorting table most people actually need: it adds stability, which decides whether a multi-key sort preserves earlier ordering.
| Algorithm | Best | Average | Worst | Aux. Space | Stable |
| :--- | :---: | :---: | :---: | :---: | :---: |
| Insertion sort | `O(n)` | `O(n²)` | `O(n²)` | `O(1)` | Yes |
| Heapsort | `O(n log n)` | `O(n log n)` | `O(n log n)` | `O(1)` | No |
| Mergesort (top-down) | `O(n log n)` | `O(n log n)` | `O(n log n)` | `O(n)` | Yes |
| Quicksort (random pivot) | `O(n log n)` | `O(n log n)` | `O(n²)` | `O(log n)` | No |
| Timsort | `O(n)` | `O(n log n)` | `O(n log n)` | `O(n)` | Yes |Data structure operations (average / worst)
One row per structure, one column per operation, with average and worst separated by a slash where they differ.
| Structure | Access | Search | Insert | Delete |
| :--- | :---: | :---: | :---: | :---: |
| Dynamic array | `O(1)` | `O(n)` | `O(n)`, end `O(1)*` | `O(n)` |
| Singly linked list | `O(n)` | `O(n)` | head `O(1)` | head `O(1)` |
| Hash table | — | `O(1)` / `O(n)` | `O(1)` / `O(n)` | `O(1)` / `O(n)` |
| Red-black tree | `O(log n)` | `O(log n)` | `O(log n)` | `O(log n)` |
| Binary heap | min `O(1)` | `O(n)` | `O(log n)` | min `O(log n)` |Graph algorithms with escaped |V| and |E|
Set notation for vertex and edge counts uses vertical bars, which must be escaped as \| even inside code spans or the row breaks.
| Algorithm | Time | Space | Assumes |
| :--- | :---: | :---: | :--- |
| BFS / DFS | `O(\|V\| + \|E\|)` | `O(\|V\|)` | Adjacency list |
| Dijkstra | `O((\|V\| + \|E\|) log \|V\|)` | `O(\|V\|)` | Binary heap, non-negative weights |
| Bellman–Ford | `O(\|V\| · \|E\|)` | `O(\|V\|)` | Negative weights allowed |
| Floyd–Warshall | `O(\|V\|³)` | `O(\|V\|²)` | All pairs, dense graphs |Common Mistakes
Listing
O(n)as the worst case for a balanced binary search tree.Self-balancing trees (AVL, red-black) guarantee
O(log n)search, insert, and delete.O(n)is the worst case of an unbalanced BST fed sorted keys; make it a separate row if you want to show the contrast.Treating amortised and average-case bounds as the same thing.
Amortised
O(1)append is a guarantee over any sequence of operations; average-caseO(1)hashing is an expectation over inputs. Mark amortised bounds with an asterisk and a footnote.Showing hash tables as
O(1)with no worst case.Include the
O(n)worst case. Some implementations narrow it — Java 8’sHashMapturns long collision chains into trees, givingO(log n)for comparable keys — so name the implementation if it matters.Writing
O(|V| + |E|)with bare pipes, which GFM reads as cell separators even inside backticks.Escape every bar as
\|(see escaping pipes), or use math with\lvert V \rvertto avoid the pipe character altogether.
Related Markdown Table Templates
Browse all 50 templatesHypothesis Testing & Statistical Analysis
Summarize inferential statistical hypotheses, sample sizes, degrees of freedom, test statistics, p-values, and empirical conclusions.
Trigonometric & Mathematical Constants Table
Reference table for standard trigonometric circle angles, radians, exact fractions, and decimal approximations for math and physics.
Machine Learning Model Benchmark Matrix
Compare machine learning and deep learning models across accuracy, precision, recall, F1 score, model parameter count, and inference latency.
Big-O Algorithmic Time & Space Complexity: Frequently Asked Questions
Why is quicksort so widely used if its worst case is O(n²)?
Its average case is O(n log n) with small constant factors and good cache behaviour, and a random or median-of-three pivot makes the worst case very unlikely. Many standard libraries use introsort, which starts with quicksort and switches to heapsort if recursion gets too deep, guaranteeing O(n log n).
Is a hash table lookup really O(1)?
On average, yes, provided the hash function spreads keys well and the table resizes to keep its load factor bounded. If many keys collide, a lookup must scan them, so the worst case is O(n) for chaining without tree buckets.
Is Big-O the same as worst case?
No. Big-O is an upper bound on a function, and you can state it for the best, average, or worst case separately. Saying “quicksort is O(n log n)” is true of its average case and false of its worst case, which is why this table has separate columns.
Should I write complexities with backticks or LaTeX math?
Backticks are portable and render the same everywhere; GitHub also renders $O(n \log n)$ as math. Pick one style for the whole table. Superscripts such as n² work in backticks as Unicode characters, while math lets you write n^2.