Computer Science Reference
Big-O Complexity Reference
Big-O describes how an algorithm's cost grows as the input grows, ignoring constants — O(1) is unaffected by size, O(log n) halves the problem each step, O(n) scales in step with it, and O(n²) becomes unusable quickly. This reference gives the time and space complexity of the data structures and algorithms interviews test.
Browse by Category
Notations
10What each growth class means in practice.
Arrays & Lists
14Contiguous and linked sequences.
Hash Tables & Sets
7Key-based lookup structures.
Trees & Heaps
15Ordered hierarchical structures.
Sorting Algorithms
12Comparison and non-comparison sorts.
Graph Algorithms
12Traversal, shortest path and spanning trees.
Searching & Misc
12Lookup and common interview routines.
All Big-O Complexity (82)
Notations (10)
What each growth class means in practice.
| Operation | Average | Notes | Worst |
|---|---|---|---|
Constant time | O(1) | Cost does not change as the input grows. Array indexing and hash lookups. At one million items, still about one step. | — |
Logarithmic time | O(log n) | Discards a fixed fraction of the input each step, so doubling the input adds one step. One million items takes about 20 steps. | — |
Square-root time | O(√n) | Appears in jump search and in block-decomposition techniques. One million items takes about 1,000 steps. | — |
Linear time | O(n) | Touches each element a constant number of times. One million items takes about one million steps — the ceiling for anything that must read all its input. | — |
Linearithmic time | O(n log n) | The proven lower bound for comparison sorting. One million items takes about 20 million steps, which is still comfortably fast. | — |
Quadratic time | O(n²) | Every element against every other — nested loops. One million items is 10¹² steps, which will not finish. Fine at n in the hundreds. | — |
Cubic time | O(n³) | Three nested loops, as in naive matrix multiplication and Floyd-Warshall. Practical only for a few hundred elements. | — |
Exponential time | O(2ⁿ) | Doubles with each added element — subset enumeration and naive recursive Fibonacci. Unusable past roughly n = 30 without memoisation. | — |
Factorial time | O(n!) | Every ordering of the input, as in brute-force travelling salesman. Unusable past about n = 12. | — |
Amortised constant | O(1)* | Occasional expensive operations averaged over many cheap ones — a dynamic array doubling its buffer. Any single call may be O(n); the average is O(1). | — |
Average
O(1)
Notes
Cost does not change as the input grows. Array indexing and hash lookups. At one million items, still about one step.
Worst
—
Average
O(log n)
Notes
Discards a fixed fraction of the input each step, so doubling the input adds one step. One million items takes about 20 steps.
Worst
—
Average
O(√n)
Notes
Appears in jump search and in block-decomposition techniques. One million items takes about 1,000 steps.
Worst
—
Average
O(n)
Notes
Touches each element a constant number of times. One million items takes about one million steps — the ceiling for anything that must read all its input.
Worst
—
Average
O(n log n)
Notes
The proven lower bound for comparison sorting. One million items takes about 20 million steps, which is still comfortably fast.
Worst
—
Average
O(n²)
Notes
Every element against every other — nested loops. One million items is 10¹² steps, which will not finish. Fine at n in the hundreds.
Worst
—
Average
O(n³)
Notes
Three nested loops, as in naive matrix multiplication and Floyd-Warshall. Practical only for a few hundred elements.
Worst
—
Average
O(2ⁿ)
Notes
Doubles with each added element — subset enumeration and naive recursive Fibonacci. Unusable past roughly n = 30 without memoisation.
Worst
—
Average
O(n!)
Notes
Every ordering of the input, as in brute-force travelling salesman. Unusable past about n = 12.
Worst
—
Average
O(1)*
Notes
Occasional expensive operations averaged over many cheap ones — a dynamic array doubling its buffer. Any single call may be O(n); the average is O(1).
Worst
—
Arrays & Lists (14)
Contiguous and linked sequences.
| Operation | Average | Notes | Worst |
|---|---|---|---|
Array · access by index | O(1) | Address arithmetic on a contiguous block — no traversal involved. | O(1) |
Array · search unsorted | O(n) | No structure to exploit, so every element may have to be examined. | O(n) |
Array · insert at index | O(n) | Every later element shifts one place to make room. | O(n) |
Array · delete at index | O(n) | Every later element shifts back to close the gap. | O(n) |
Dynamic array · append | O(1)* | Amortised: writing is constant until the buffer is full, then everything is copied to a larger one. Python list, Java ArrayList, C++ vector. | O(n) |
Dynamic array · pop from end | O(1) | Nothing shifts, so removing the last element is genuinely constant. | O(1) |
Singly linked list · access | O(n) | No indexing — reaching position k means following k pointers from the head. | O(n) |
Singly linked list · insert at head | O(1) | Point the new node at the old head and move the head pointer. No shifting anywhere. | O(1) |
Singly linked list · delete at head | O(1) | Advance the head pointer past the removed node. | O(1) |
Singly linked list · delete a known node | O(n) | The previous node must be found to relink it, and a singly linked list cannot walk backwards. | O(n) |
Doubly linked list · delete a known node | O(1) | Each node knows its predecessor, so relinking needs no search. This is what makes an LRU cache O(1). | O(1) |
Stack · push / pop / peek | O(1) | All work happens at one end, whether backed by an array or a linked list. | O(1) |
Queue · enqueue / dequeue | O(1) | Constant at both ends when implemented as a linked list or a circular buffer. A naive array queue is O(n) to dequeue. | O(1) |
Deque · push / pop either end | O(1) | Amortised constant at both ends. Python collections.deque, Java ArrayDeque. | O(1) |
Average
O(1)
Notes
Address arithmetic on a contiguous block — no traversal involved.
Worst
O(1)
Average
O(n)
Notes
No structure to exploit, so every element may have to be examined.
Worst
O(n)
Average
O(n)
Notes
Every later element shifts one place to make room.
Worst
O(n)
Average
O(n)
Notes
Every later element shifts back to close the gap.
Worst
O(n)
Average
O(1)*
Notes
Amortised: writing is constant until the buffer is full, then everything is copied to a larger one. Python list, Java ArrayList, C++ vector.
Worst
O(n)
Average
O(1)
Notes
Nothing shifts, so removing the last element is genuinely constant.
Worst
O(1)
Average
O(n)
Notes
No indexing — reaching position k means following k pointers from the head.
Worst
O(n)
Average
O(1)
Notes
Point the new node at the old head and move the head pointer. No shifting anywhere.
Worst
O(1)
Average
O(1)
Notes
Advance the head pointer past the removed node.
Worst
O(1)
Average
O(n)
Notes
The previous node must be found to relink it, and a singly linked list cannot walk backwards.
Worst
O(n)
Average
O(1)
Notes
Each node knows its predecessor, so relinking needs no search. This is what makes an LRU cache O(1).
Worst
O(1)
Average
O(1)
Notes
All work happens at one end, whether backed by an array or a linked list.
Worst
O(1)
Average
O(1)
Notes
Constant at both ends when implemented as a linked list or a circular buffer. A naive array queue is O(n) to dequeue.
Worst
O(1)
Average
O(1)
Notes
Amortised constant at both ends. Python collections.deque, Java ArrayDeque.
Worst
O(1)
Hash Tables & Sets (7)
Key-based lookup structures.
| Operation | Average | Notes | Worst |
|---|---|---|---|
Hash table · lookup | O(1) | Hash the key, go straight to the bucket. Degrades to a linear scan when every key collides. | O(n) |
Hash table · insert | O(1)* | Amortised: constant until the load factor is exceeded and the table is rehashed, which is O(n). | O(n) |
Hash table · delete | O(1) | Same bucket lookup as a search, then unlink. Open-addressing tables need tombstones to stay correct. | O(n) |
Java HashMap · lookup | O(1) | Since Java 8 a bucket with many collisions becomes a red-black tree, so the worst case is O(log n) rather than O(n). | O(log n) |
Hash set · add / contains | O(1) | A hash table storing only keys. The reason deduplication is usually written with a set. | O(n) |
Bloom filter · add / query | O(k) | k hash functions, independent of the number of items stored. Says "definitely not present" or "probably present", and cannot delete. | O(k) |
LRU cache · get / put | O(1) | A hash map for lookup plus a doubly linked list for recency. Both halves are needed to hit O(1). | O(1) |
Average
O(1)
Notes
Hash the key, go straight to the bucket. Degrades to a linear scan when every key collides.
Worst
O(n)
Average
O(1)*
Notes
Amortised: constant until the load factor is exceeded and the table is rehashed, which is O(n).
Worst
O(n)
Average
O(1)
Notes
Same bucket lookup as a search, then unlink. Open-addressing tables need tombstones to stay correct.
Worst
O(n)
Average
O(1)
Notes
Since Java 8 a bucket with many collisions becomes a red-black tree, so the worst case is O(log n) rather than O(n).
Worst
O(log n)
Average
O(1)
Notes
A hash table storing only keys. The reason deduplication is usually written with a set.
Worst
O(n)
Average
O(k)
Notes
k hash functions, independent of the number of items stored. Says "definitely not present" or "probably present", and cannot delete.
Worst
O(k)
Average
O(1)
Notes
A hash map for lookup plus a doubly linked list for recency. Both halves are needed to hit O(1).
Worst
O(1)
Trees & Heaps (15)
Ordered hierarchical structures.
| Operation | Average | Notes | Worst |
|---|---|---|---|
Binary search tree · search | O(log n) | Halves the range at each node while the tree is balanced. Inserting sorted data produces a linked list, hence the worst case. | O(n) |
Binary search tree · insert / delete | O(log n) | Follows the same path as a search, then relinks. Degenerates alongside search when the tree is unbalanced. | O(n) |
AVL tree · search / insert / delete | O(log n) | Rebalances by rotation after every write, keeping height tightly bounded. More rotations than red-black, faster lookups. | O(log n) |
Red-black tree · search / insert / delete | O(log n) | Looser balance than AVL, so fewer rotations on write. Backs Java TreeMap and C++ std::map. | O(log n) |
B-tree · search / insert / delete | O(log n) | High branching factor keeps the tree shallow, so each level is one disk or page read. The structure behind database indexes. | O(log n) |
Binary heap · find min | O(1) | The minimum is always the root, so peeking costs nothing. | O(1) |
Binary heap · insert | O(log n) | Place at the end and sift upwards through at most the height of the tree. | O(log n) |
Binary heap · extract min | O(log n) | Move the last element to the root and sift down. | O(log n) |
Binary heap · build from array | O(n) | Heapify bottom-up is linear, not O(n log n) — most nodes are near the leaves and sift down barely at all. | O(n) |
Fibonacci heap · decrease key | O(1)* | Amortised constant, which is what makes the theoretical bound on Dijkstra better. Constant factors are poor enough that binary heaps usually win in practice. | O(log n) |
Trie · insert / search | O(m) | Depends on key length m, not on how many keys are stored — so lookup does not slow down as the dictionary grows. | O(m) |
Trie · prefix search | O(m + k) | Walk the prefix, then collect the k results beneath it. The reason autocomplete uses a trie. | O(m + k) |
Segment tree · query / update | O(log n) | Range queries and point updates on an array. Building it is O(n). | O(log n) |
Fenwick tree · query / update | O(log n) | Prefix sums with far less memory and code than a segment tree, at the cost of flexibility. | O(log n) |
Skip list · search / insert / delete | O(log n) | Randomised layers give balanced-tree performance with much simpler code. Used in Redis sorted sets. | O(n) |
Average
O(log n)
Notes
Halves the range at each node while the tree is balanced. Inserting sorted data produces a linked list, hence the worst case.
Worst
O(n)
Average
O(log n)
Notes
Follows the same path as a search, then relinks. Degenerates alongside search when the tree is unbalanced.
Worst
O(n)
Average
O(log n)
Notes
Rebalances by rotation after every write, keeping height tightly bounded. More rotations than red-black, faster lookups.
Worst
O(log n)
Average
O(log n)
Notes
Looser balance than AVL, so fewer rotations on write. Backs Java TreeMap and C++ std::map.
Worst
O(log n)
Average
O(log n)
Notes
High branching factor keeps the tree shallow, so each level is one disk or page read. The structure behind database indexes.
Worst
O(log n)
Average
O(1)
Notes
The minimum is always the root, so peeking costs nothing.
Worst
O(1)
Average
O(log n)
Notes
Place at the end and sift upwards through at most the height of the tree.
Worst
O(log n)
Average
O(log n)
Notes
Move the last element to the root and sift down.
Worst
O(log n)
Average
O(n)
Notes
Heapify bottom-up is linear, not O(n log n) — most nodes are near the leaves and sift down barely at all.
Worst
O(n)
Average
O(1)*
Notes
Amortised constant, which is what makes the theoretical bound on Dijkstra better. Constant factors are poor enough that binary heaps usually win in practice.
Worst
O(log n)
Average
O(m)
Notes
Depends on key length m, not on how many keys are stored — so lookup does not slow down as the dictionary grows.
Worst
O(m)
Average
O(m + k)
Notes
Walk the prefix, then collect the k results beneath it. The reason autocomplete uses a trie.
Worst
O(m + k)
Average
O(log n)
Notes
Range queries and point updates on an array. Building it is O(n).
Worst
O(log n)
Average
O(log n)
Notes
Prefix sums with far less memory and code than a segment tree, at the cost of flexibility.
Worst
O(log n)
Average
O(log n)
Notes
Randomised layers give balanced-tree performance with much simpler code. Used in Redis sorted sets.
Worst
O(n)
Sorting Algorithms (12)
Comparison and non-comparison sorts.
| Operation | Average | Notes | Worst |
|---|---|---|---|
Quicksort | O(n log n) | Fastest in practice thanks to cache behaviour and in-place partitioning. O(n²) when pivots are consistently poor; O(log n) stack space. Not stable. | O(n²) |
Introsort | O(n log n) | Quicksort that switches to heapsort once recursion runs too deep, removing the O(n²) worst case. This is what C++ std::sort actually is. | O(n log n) |
Mergesort | O(n log n) | Guaranteed bound and stable, at the cost of O(n) extra space. The right choice for linked lists and external sorting. | O(n log n) |
Heapsort | O(n log n) | Guaranteed bound in O(1) space, but poor locality makes it slower than quicksort in practice. Not stable. | O(n log n) |
Timsort | O(n log n) | Detects runs already in order, so nearly sorted input approaches O(n). Stable, O(n) space. Used by Python sorted() and Java Arrays.sort on objects. | O(n log n) |
Insertion sort | O(n²) | O(n) on nearly sorted input and very low overhead, so real sorts fall back to it for small partitions. Stable, in place. | O(n²) |
Bubble sort | O(n²) | O(n) on already sorted input with an early exit. Taught for the idea, never used in practice. | O(n²) |
Selection sort | O(n²) | Always O(n²) regardless of input, but makes only O(n) writes — occasionally relevant when writes are expensive. | O(n²) |
Shell sort | O(n log² n) | Insertion sort over decreasing gaps. The exact bound depends on the gap sequence chosen. | O(n²) |
Counting sort | O(n + k) | Beats O(n log n) by not comparing at all, but needs O(k) space for the value range. Only viable when k is small. | O(n + k) |
Radix sort | O(d·(n + k)) | Counting sort applied one digit at a time, d digits deep. Linear when key width is fixed, as for 32-bit integers. | O(d·(n + k)) |
Bucket sort | O(n + k) | Assumes input is spread evenly across buckets. Collapses to O(n²) when everything lands in one bucket. | O(n²) |
Average
O(n log n)
Notes
Fastest in practice thanks to cache behaviour and in-place partitioning. O(n²) when pivots are consistently poor; O(log n) stack space. Not stable.
Worst
O(n²)
Average
O(n log n)
Notes
Quicksort that switches to heapsort once recursion runs too deep, removing the O(n²) worst case. This is what C++ std::sort actually is.
Worst
O(n log n)
Average
O(n log n)
Notes
Guaranteed bound and stable, at the cost of O(n) extra space. The right choice for linked lists and external sorting.
Worst
O(n log n)
Average
O(n log n)
Notes
Guaranteed bound in O(1) space, but poor locality makes it slower than quicksort in practice. Not stable.
Worst
O(n log n)
Average
O(n log n)
Notes
Detects runs already in order, so nearly sorted input approaches O(n). Stable, O(n) space. Used by Python sorted() and Java Arrays.sort on objects.
Worst
O(n log n)
Average
O(n²)
Notes
O(n) on nearly sorted input and very low overhead, so real sorts fall back to it for small partitions. Stable, in place.
Worst
O(n²)
Average
O(n²)
Notes
O(n) on already sorted input with an early exit. Taught for the idea, never used in practice.
Worst
O(n²)
Average
O(n²)
Notes
Always O(n²) regardless of input, but makes only O(n) writes — occasionally relevant when writes are expensive.
Worst
O(n²)
Average
O(n log² n)
Notes
Insertion sort over decreasing gaps. The exact bound depends on the gap sequence chosen.
Worst
O(n²)
Average
O(n + k)
Notes
Beats O(n log n) by not comparing at all, but needs O(k) space for the value range. Only viable when k is small.
Worst
O(n + k)
Average
O(d·(n + k))
Notes
Counting sort applied one digit at a time, d digits deep. Linear when key width is fixed, as for 32-bit integers.
Worst
O(d·(n + k))
Average
O(n + k)
Notes
Assumes input is spread evenly across buckets. Collapses to O(n²) when everything lands in one bucket.
Worst
O(n²)
Graph Algorithms (12)
Traversal, shortest path and spanning trees.
| Operation | Average | Notes | Worst |
|---|---|---|---|
Breadth-first search | O(V + E) | Visits every vertex and edge once. Finds the shortest path in an unweighted graph; O(V) queue space. | O(V + E) |
Depth-first search | O(V + E) | Same bound as BFS. Used for cycle detection, topological order and connected components; O(V) stack depth. | O(V + E) |
Dijkstra (binary heap) | O((V + E) log V) | Shortest paths from one source with non-negative weights. The usual implementation. | O((V + E) log V) |
Dijkstra (Fibonacci heap) | O(E + V log V) | The best known bound, thanks to O(1) amortised decrease-key. Rarely worth the constant factors in practice. | O(E + V log V) |
Bellman-Ford | O(V·E) | Slower than Dijkstra but handles negative edge weights and detects negative cycles. | O(V·E) |
Floyd-Warshall | O(V³) | Shortest paths between every pair of vertices, in O(V²) space. Practical up to a few hundred vertices. | O(V³) |
A* search | O(E) | Dijkstra guided by a heuristic. With an admissible heuristic it is optimal; with a poor one it degrades towards exponential. | O(bᵈ) |
Kruskal (MST) | O(E log E) | Dominated by sorting the edges. Uses union-find to reject edges that would form a cycle. | O(E log E) |
Prim (MST, binary heap) | O(E log V) | Grows one tree outwards. Preferred over Kruskal on dense graphs. | O(E log V) |
Topological sort | O(V + E) | Orders a DAG so every edge points forwards. Kahn's algorithm also detects cycles. | O(V + E) |
Union-Find (path compression + rank) | O(α(n)) | The inverse Ackermann function is below 5 for any input that fits in a computer, so this is constant in every practical sense. | O(α(n)) |
Tarjan (strongly connected components) | O(V + E) | Finds all SCCs in a single depth-first pass. | O(V + E) |
Average
O(V + E)
Notes
Visits every vertex and edge once. Finds the shortest path in an unweighted graph; O(V) queue space.
Worst
O(V + E)
Average
O(V + E)
Notes
Same bound as BFS. Used for cycle detection, topological order and connected components; O(V) stack depth.
Worst
O(V + E)
Average
O((V + E) log V)
Notes
Shortest paths from one source with non-negative weights. The usual implementation.
Worst
O((V + E) log V)
Average
O(E + V log V)
Notes
The best known bound, thanks to O(1) amortised decrease-key. Rarely worth the constant factors in practice.
Worst
O(E + V log V)
Average
O(V·E)
Notes
Slower than Dijkstra but handles negative edge weights and detects negative cycles.
Worst
O(V·E)
Average
O(V³)
Notes
Shortest paths between every pair of vertices, in O(V²) space. Practical up to a few hundred vertices.
Worst
O(V³)
Average
O(E)
Notes
Dijkstra guided by a heuristic. With an admissible heuristic it is optimal; with a poor one it degrades towards exponential.
Worst
O(bᵈ)
Average
O(E log E)
Notes
Dominated by sorting the edges. Uses union-find to reject edges that would form a cycle.
Worst
O(E log E)
Average
O(E log V)
Notes
Grows one tree outwards. Preferred over Kruskal on dense graphs.
Worst
O(E log V)
Average
O(V + E)
Notes
Orders a DAG so every edge points forwards. Kahn's algorithm also detects cycles.
Worst
O(V + E)
Average
O(α(n))
Notes
The inverse Ackermann function is below 5 for any input that fits in a computer, so this is constant in every practical sense.
Worst
O(α(n))
Average
O(V + E)
Notes
Finds all SCCs in a single depth-first pass.
Worst
O(V + E)
Searching & Misc (12)
Lookup and common interview routines.
| Operation | Average | Notes | Worst |
|---|---|---|---|
Linear search | O(n) | Checks each element in turn. The only option on unsorted data without an index. | O(n) |
Binary search | O(log n) | Halves the range each comparison. Requires sorted, randomly accessible data — it is O(n) on a linked list. | O(log n) |
Jump search | O(√n) | Steps forward in blocks then scans one. Beats linear search when random access is expensive. | O(√n) |
Interpolation search | O(log log n) | Estimates where the key should be from its value. Beats binary search on uniformly distributed data, degrades to O(n) on skewed data. | O(n) |
Exponential search | O(log n) | Doubles a bound until it passes the key, then binary searches inside it. For unbounded or very large sorted input. | O(log n) |
Naive substring search | O(n·m) | Tries every alignment of the pattern. Fine for short patterns, poor on repetitive text. | O(n·m) |
KMP substring search | O(n + m) | Precomputes a prefix table so the text pointer never moves backwards. Guaranteed linear. | O(n + m) |
Rabin-Karp | O(n + m) | Rolling hash comparison. Degrades to O(n·m) when hashes collide often, but excels at searching many patterns at once. | O(n·m) |
Boyer-Moore | O(n / m) | Skips ahead using mismatch tables, so longer patterns are faster. The basis of most real grep implementations. | O(n·m) |
Two pointers | O(n) | One pass with two indices moving through sorted data. Replaces a nested loop in pair-sum and interval problems. | O(n) |
Sliding window | O(n) | Each element enters and leaves the window once. Turns an O(n²) subarray scan into a single pass. | O(n) |
Binary search on the answer | O(n log R) | Binary search over the range of possible answers R, testing feasibility in O(n). The standard trick for minimax problems. | O(n log R) |
Average
O(n)
Notes
Checks each element in turn. The only option on unsorted data without an index.
Worst
O(n)
Average
O(log n)
Notes
Halves the range each comparison. Requires sorted, randomly accessible data — it is O(n) on a linked list.
Worst
O(log n)
Average
O(√n)
Notes
Steps forward in blocks then scans one. Beats linear search when random access is expensive.
Worst
O(√n)
Average
O(log log n)
Notes
Estimates where the key should be from its value. Beats binary search on uniformly distributed data, degrades to O(n) on skewed data.
Worst
O(n)
Average
O(log n)
Notes
Doubles a bound until it passes the key, then binary searches inside it. For unbounded or very large sorted input.
Worst
O(log n)
Average
O(n·m)
Notes
Tries every alignment of the pattern. Fine for short patterns, poor on repetitive text.
Worst
O(n·m)
Average
O(n + m)
Notes
Precomputes a prefix table so the text pointer never moves backwards. Guaranteed linear.
Worst
O(n + m)
Average
O(n + m)
Notes
Rolling hash comparison. Degrades to O(n·m) when hashes collide often, but excels at searching many patterns at once.
Worst
O(n·m)
Average
O(n / m)
Notes
Skips ahead using mismatch tables, so longer patterns are faster. The basis of most real grep implementations.
Worst
O(n·m)
Average
O(n)
Notes
One pass with two indices moving through sorted data. Replaces a nested loop in pair-sum and interval problems.
Worst
O(n)
Average
O(n)
Notes
Each element enters and leaves the window once. Turns an O(n²) subarray scan into a single pass.
Worst
O(n)
Average
O(n log R)
Notes
Binary search over the range of possible answers R, testing feasibility in O(n). The standard trick for minimax problems.
Worst
O(n log R)
Frequently Asked Questions
What does O(1) mean?
O(1) means constant time — the operation takes about the same time no matter how large the input is. Reading an array element by index or looking up a key in a hash table are O(1): the cost does not grow when the collection does.
Why is O(log n) so much better than O(n)?
A logarithmic algorithm discards half the remaining input at each step, so doubling the input adds only one more step. Searching a sorted array of a billion items takes about 30 comparisons with binary search, against a billion with a linear scan.
What is the fastest sorting algorithm?
No comparison sort can beat O(n log n) on average, and quicksort, mergesort and heapsort all hit it. Quicksort is usually fastest in practice because of cache behaviour, mergesort is stable and predictable, and counting or radix sort can beat O(n log n) only because they do not compare elements.
Does Big-O measure actual running time?
No. It describes how cost grows with input size and deliberately drops constants and lower-order terms, so an O(n) algorithm can be slower than an O(n²) one on small inputs. It tells you which algorithm wins as the data gets large, not which is faster today.