What does Big-O actually measure?

Big-O describes how an algorithm's running time or memory grows as the input size n grows, keeping only the dominant term and ignoring constant factors. O(2n) and O(n + 5) are both just O(n). It is an upper bound on growth rate, useful for comparing how algorithms scale rather than predicting exact milliseconds.

Why is quicksort O(n log n) if its worst case is O(n²)?

Quicksort is O(n log n) on average and in the best case, but degenerates to O(n²) when pivots are consistently poor, such as always picking the first element of an already-sorted array. Randomized or median-of-three pivoting makes the bad case astronomically unlikely, so it is treated as O(n log n) in practice.

What is the difference between average and amortized complexity?

Average case is the expected cost over random inputs. Amortized cost is the average cost per operation over a worst-case sequence of operations. A dynamic-array append is amortized O(1): most appends are constant, and the occasional O(n) resize is spread across many cheap appends so the long-run average stays constant.

Does lower Big-O always mean faster?

Not for small inputs. Big-O hides constant factors, so an O(n²) insertion sort can beat an O(n log n) merge sort on tiny or nearly-sorted arrays, which is why real sort implementations switch to insertion sort below a threshold. Big-O matters most as n grows large.

Why do hash tables show O(n) worst case?

Hash lookups are O(1) on average, but if many keys collide into the same bucket — through a poor hash function or an adversarial input — the bucket degrades to a linear scan, making the worst case O(n). Good hashing and load-factor management keep this from happening in practice.

Big-O Complexity Reference

Email me this result

Get this tool's output sent to your inbox, plus one useful tool a week. No spam, unsubscribe any time.

Big-O notation summarizes how an algorithm scales as its input grows. Knowing the complexity of the operation you are about to run is the fastest way to predict whether code will stay fast at scale. This reference collects the standard complexities for the algorithms and data-structure operations you meet daily.

How it works

For each entry you get up to four figures:

Best — the most favorable input (often nearly-sorted or an immediate hit).
Average — expected cost over typical input.
Worst — the pathological case you must design around.
Space — additional memory beyond the input itself.

Lower-order terms and constants drop out: O(n + log n) is reported as O(n), and O(2n) as O(n). The goal is the growth rate, not an exact count.

Example

Choosing a sort: merge sort guarantees O(n log n) time but needs O(n) auxiliary memory and is stable. Heapsort also guarantees O(n log n) but sorts in place with O(1) extra space, at the cost of stability. Quicksort is usually fastest in practice but risks O(n²) without good pivoting. The table lets you weigh these side by side.

Notes

Amortized analysis explains why a dynamic-array append is “O(1)” despite occasional O(n) resizes — the cost is spread across many cheap operations.
Graph complexities are written in terms of V (vertices) and E (edges); traversal is O(V + E), Dijkstra with a binary heap is O((V + E) log V).
Non-comparison sorts (counting, radix) beat the O(n log n) comparison lower bound only because they exploit bounded key ranges.
Always check whether your real inputs hit the worst case before optimizing — the average case is what usually runs.