Big-O Cheat Sheet

What is on the page

The page, built by a software engineer (ericdrowell on GitHub) who says he made it after spending hours collecting these numbers while preparing for his own interviews, has three parts:

• Big-O complexity chart: a colour-coded plot of the common growth rates, from "excellent" (constant and logarithmic) through "fair" and "bad" to "horrible" (factorial), so you can see how quickly quadratic pulls away from linearithmic.
• Common data structure operations: average and worst-case time for access, search, insertion and deletion, plus worst-case space, for arrays, stacks, queues, singly and doubly linked lists, skip lists, hash tables, binary search trees, Cartesian trees, B-trees, red-black trees, splay trees, AVL trees and KD trees.
• Array sorting algorithms: best, average and worst-case time and worst-case space for quicksort, mergesort, Timsort, heapsort, bubble, insertion, selection, tree, shell, bucket, radix and counting sort, and cubesort.

There is a downloadable PDF version, and the tables are maintained on GitHub, where the page lists around 50 contributors.

What it does not include

Heaps and priority queues, tries and graphs have no rows, so there is nothing here on heap push and pop, Dijkstra or BFS costs. Search algorithms such as binary search are not tabulated either. The cells also flatten nuance: array "insertion" is listed as linear because of shifting, which is true in the middle and not at the end, and hash table costs assume a good hash function. Treat it as a quick check, not as the explanation.

How to use it well

• After each practice problem, state your solution's time and space complexity out loud first, then check the relevant row. Stop checking once you are consistently right.
• Learn why, not just what. For every cell you get wrong, find out why it has that value. Interviewers ask the follow-up ("why is that the worst case?"), and a memorised table does not answer it.
• Use the chart when choosing between approaches. Seeing how far n log n is from n squared at a million elements makes the trade-off concrete when you justify a choice.
• Do not cram it the night before. It is most useful as a companion during practice over weeks.

Pair it with

For the reasoning behind the numbers, pair it with a course or chapter on complexity analysis (for example the Big-O material in Grokking Algorithm Complexity and Big-O, or the analysis chapters of Princeton's Algorithms course). For heaps, graphs and tries, a data structures course or VisuAlgo's animations fill the gaps.

Common questions

Is it still accurate? The standard values in the tables are well established and have not changed. The GitHub repository's last commit was in 2019, so it is a stable reference rather than an actively updated one.

Do I need to memorise it? No. You need to be able to derive the common entries (arrays, hash tables, balanced trees, the main sorts) and explain them. The rest is there when you need it.

Best for: everyone practising coding problems. Keep it bookmarked during practice, not the night before.