How to use the Big O Complexity Cheat Sheet
- 1. Pick a tableData structures, sorting or algorithms.
- 2. Try your nEnter an input size to see steps and rough times for each complexity class.
- 3. DownloadSave the whole sheet as a text file for revision.
What the tables cover
- Data structures: access, search, insert, delete and space for arrays, dynamic arrays, linked lists, stacks, queues, hash tables, BSTs, AVL and red-black trees, heaps and tries. Where average and worst cases differ, like hash tables and plain BSTs, both are shown.
- Sorting: best, average and worst time, extra space and stability for bubble, selection, insertion, merge, quick, heap, counting, radix and Timsort (used by Python's sort and Java for objects).
- Algorithms: binary search, BFS and DFS, Dijkstra, Bellman-Ford, Floyd-Warshall, Kruskal, Prim, topological sort, KMP and exponential cases like generating subsets.
The chart shows how O(1), O(log n), O(n), O(n log n), O(n²), O(n³) and O(2ⁿ) grow for small n. The curves for 2ⁿ and n² shoot off the top almost at once.
Worked example: will my solution pass?
Online judges and coding rounds often allow about 1 second, and a common rule of thumb is around 10⁸ simple steps per second. Enter n = 100,000 in the calculator:
- O(n log n) is about 1.66 million steps, roughly 16.6 ms: comfortably fast.
- O(n²) is 10¹⁰ steps, about 1.7 minutes (100 seconds): far too slow.
So for n = 10⁵, an O(n²) nested loop will time out and you need sorting, a hash map or two pointers to get to O(n log n) or O(n). The estimate ignores constant factors and the language you use, so treat it as a guide: Python is often 10 to 50 times slower per step than C++, which is why you can switch the speed to 10⁷.
Frequently asked questions
What does amortised O(1) mean?
Most appends to a dynamic array are O(1), with an occasional O(n) resize. Averaged over many appends, each costs O(1).
Is O(log n) base 2?
Big-O ignores the base, because logs of different bases differ only by a constant factor. Base 2 is the usual one for halving algorithms.
Why is quicksort used if its worst case is O(n²)?
Its average case is O(n log n) with small constants and good cache use, and random or median-of-three pivots make the worst case very unlikely.
Is the big o complexity cheat sheet free to use?
Yes, the big o complexity cheat sheet is free and costs nothing. Downloading the sheet shows a short form for your name and WhatsApp number one time; once that's done, this tool and every other Uncodemy tool open with no form.