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.

What is the Big-O Complexity Reference?

Searchable Big-O complexity reference: best, average and worst-case time plus space complexity for sorting, searching, data-structure operations and graph algorithms, with a note on when each worst case bites. It runs free in your browser on Gera Tools, with nothing uploaded.

Big-O Complexity Reference

Name: Big-O Complexity Reference
Creator: Gera Tools
License: https://creativecommons.org/licenses/by/4.0/

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.

A practical guide to reading complexity classes

Understanding what each Big-O class means in practice helps when deciding whether to optimise. Here is a rough mental model:

Class	Name	What it means in practice
`O(1)`	Constant	Does not depend on input size at all. Hash table lookup, array index access.
`O(log n)`	Logarithmic	Doubles the work every time input squares. Binary search on 1,000 items takes roughly 10 steps; on 1,000,000 it takes roughly 20.
`O(n)`	Linear	One pass through the data. Unavoidable when you must inspect every element at least once.
`O(n log n)`	Linearithmic	The best you can do for comparison-based sorting. Merge sort, heapsort, and typical quicksort all land here.
`O(n²)`	Quadratic	Fine for hundreds of items; painful for tens of thousands. Bubble sort, insertion sort, naive duplicate detection.
`O(2ⁿ)`	Exponential	Feasible only for tiny inputs. Brute-force combinatorial search, recursive Fibonacci without memoisation.

Sorting algorithms compared

Sorting is where complexity differences are most visible day-to-day:

Merge sort is the safe default: guaranteed O(n log n) in all cases, stable, but requires O(n) extra memory. Preferred for linked lists and when stability matters (preserving equal elements’ original order).
Quicksort is the practical leader in cache performance and constant factors, but its O(n²) worst case on already-sorted or adversarial input is avoided by randomised pivot selection. JavaScript’s Array.prototype.sort and Python’s Timsort both use variations that approach this.
Heapsort gives guaranteed O(n log n) with O(1) extra space, but poor cache locality makes it slower than quicksort on typical hardware despite the same asymptotic class.
Insertion sort is O(n²) but with a tiny constant, which is why every practical implementation of merge or quicksort switches to insertion sort below a threshold of roughly 10–20 elements.

Data structure operations at a glance

The choice of data structure determines the complexity of every operation you do on it:

An array gives O(1) indexed access and O(n) search (unsorted) or O(log n) search (sorted).
A linked list gives O(1) insertion at a known position but O(n) access to a position by index.
A hash table gives O(1) average lookup, insert, and delete — but O(n) in a pathological worst case from key collisions.
A binary search tree gives O(log n) average operations but O(n) worst case on a degenerate (unbalanced) tree. Self-balancing variants (AVL, red-black) maintain O(log n) worst case.
A heap gives O(log n) insert and extract-min/max, and O(1) peek — making it the natural choice for priority queues.