Dev Tool · Algorithm Complexity

Big O Cheat Sheet & Time Complexity Calculator

Pick an algorithm or data structure. See its time and space complexity, when to use it, and roughly how many operations it'll take for your input size. Self-contained, no signup, no tracking beyond Plausible.

Try 100, 1,000, 10,000, 1,000,000. The operation count below estimates a rough order-of-magnitude steps for the worst case.
Quicksort
Divide-and-conquer sort. Fast in practice, in-place.
Estimated operations for n = 1,000 (worst case)
—
—

When to use it

—

The Big O Tiers (from best to worst)

A mental model for what's fast, what's acceptable, and what's about to make your pager go off.

Excellent
O(1)
Constant time. Hash map lookup, array index, stack push. Doesn't depend on input size.
Excellent
O(log n)
Logarithmic. Binary search, balanced tree operations. Doubling n adds one step.
Good
O(n)
Linear. Single pass over input. Reading a file, summing a list.
Good
O(n log n)
Linearithmic. The bar for a good sort. Merge sort, heap sort, modern quicksort.
Fair
O(n²)
Quadratic. Nested loops. Bubble sort, naive comparison-of-all-pairs. Fine for n < 1,000.
Bad
O(n³)
Cubic. Naive matrix multiply. Avoid for anything but small inputs.
Bad
O(2ⁿ)
Exponential. Brute-force subset enumeration. Only acceptable for n ≲ 20.
Terrible
O(n!)
Factorial. Traveling salesman brute force. Only acceptable for n ≲ 10.

Common Data Structure Operations

Average and worst-case time complexity for the operations you actually use day-to-day.

StructureAccessSearchInsertDeleteSpace
ArrayO(1)O(n)O(n)O(n)O(n)
Dynamic ArrayO(1)O(n)O(1)*O(n)O(n)
Linked ListO(n)O(n)O(1)O(1)O(n)
Doubly Linked ListO(n)O(n)O(1)O(1)O(n)
StackO(n)O(n)O(1)O(1)O(n)
QueueO(n)O(n)O(1)O(1)O(n)
Hash TableN/AO(1) / O(n)O(1) / O(n)O(1) / O(n)O(n)
Binary Search TreeO(log n) / O(n)O(log n) / O(n)O(log n) / O(n)O(log n) / O(n)O(n)
AVL / Red-Black TreeO(log n)O(log n)O(log n)O(log n)O(n)
B-TreeO(log n)O(log n)O(log n)O(log n)O(n)
Heap (Binary)O(1)†O(n)O(log n)O(log n)O(n)
TrieO(k)O(k)O(k)O(k)O(n·k)
Skip ListO(log n)O(log n)O(log n)O(log n)O(n log n)

* amortized for dynamic array append. † heap O(1) "access" is only for the min/max (peek). k = key length for trie. "O(x) / O(y)" = average / worst.

Common Sorting Algorithms

Best, average, worst case time and whether the sort is in-place and stable.

AlgorithmBestAverageWorstSpaceStable?
Bubble SortO(n)O(n²)O(n²)O(1)Yes
Insertion SortO(n)O(n²)O(n²)O(1)Yes
Selection SortO(n²)O(n²)O(n²)O(1)No
Merge SortO(n log n)O(n log n)O(n log n)O(n)Yes
QuicksortO(n log n)O(n log n)O(n²)O(log n)No
Heap SortO(n log n)O(n log n)O(n log n)O(1)No
TimsortO(n)O(n log n)O(n log n)O(n)Yes
Radix SortO(nk)O(nk)O(nk)O(n+k)Yes
Counting SortO(n+k)O(n+k)O(n+k)O(k)Yes
Bucket SortO(n+k)O(n+k)O(n²)O(n)Yes

Building a portfolio while you're at it?

Browse 359+ project ideas (with difficulty + tech stack tags) or check current engineering openings.

Portfolio Projects → Engineering Jobs →

FAQ

What is Big O notation?+
Big O describes how an algorithm's runtime or space grows as the input size grows. O(1) is constant, O(n) is linear, O(n log n) is the typical bar for a good sort, O(n²) is acceptable only for small inputs, and O(2ⁿ) or O(n!) are usually only acceptable for very small n.
What's the difference between best, average, and worst case?+
Best is the runtime on an ideal input. Worst is on an adversarial input. Average is the expected runtime over random inputs. When people say "Big O" without qualification they usually mean worst case — the bound that matters for system design, since you have to plan for inputs you don't control.
Why does quicksort have O(n²) worst case if it's usually faster than merge sort?+
Quicksort's worst case is when the pivot is consistently the smallest or largest element — what naive quicksort does on already-sorted input. Modern implementations detect this and switch to heap sort (introsort) for O(n log n) worst case. Quicksort is faster in practice because it partitions in-place — better cache locality than merge sort's temporary arrays.
When should I use a hash map vs a binary search tree?+
Hash map for O(1) lookup when you only need exact matches and don't care about order. Tree (balanced — Red-Black or AVL) for O(log n) lookup when you also need range queries, ordered iteration, or predecessor/successor operations.
Is O(n log n) always faster than O(n²)?+
Asymptotically yes, but constants matter for small inputs. Insertion sort (O(n²)) is faster than merge sort (O(n log n)) for arrays under roughly 20–50 elements because the hidden constant is much smaller. That's why production sort implementations switch to insertion sort for small subarrays.
What's amortized complexity?+
The average cost of an operation when you spread expensive occasional operations across many cheap ones. Dynamic arrays have O(1) amortized append even though occasionally an append triggers an O(n) resize — rare expensive operations average out over a long sequence of cheap ones.