Nexus Learn

Big-O cheat sheet

The time complexity of common data structures and sorting algorithms on one page. Handy for exams, assignments and coding interviews.

Growth rates, from fastest to slowest

Big-ONameTypical exampleFor large n
O(1)ConstantArray access by index, hash table lookupExcellent
O(log n)LogarithmicBinary search, balanced tree lookupExcellent
O(n)LinearScanning a list, linear searchGood
O(n log n)LinearithmicMerge sort, heap sortFair
O(n^2)QuadraticBubble sort, nested loops over the dataPoor
O(2^n)ExponentialTrying every subset, naive recursive FibonacciVery poor
O(n!)FactorialTrying every ordering, brute-force travelling salesmanVery poor

Data structure operations

StructureAccessSearchInsertDelete
ArrayO(1)O(n)O(n)O(n)
Singly linked listO(n)O(n)O(1) at the headO(n), or O(1) if you hold the node
StackO(n)O(n)O(1) pushO(1) pop
QueueO(n)O(n)O(1) enqueueO(1) dequeue
Hash table (average)n/aO(1)O(1)O(1)
Binary search tree (balanced)O(log n)O(log n)O(log n)O(log n)
Binary search tree (worst case)O(n)O(n)O(n)O(n)
Binary heapO(n)O(n)O(log n)O(log n) extract min or max

For stacks and queues the useful operations are push and pop (or enqueue and dequeue), which take constant time. A hash table has no ordered access, and its worst case is O(n) if many keys collide.

Sorting algorithms

AlgorithmBestAverageWorstExtra spaceStable
Bubble sortO(n)O(n^2)O(n^2)O(1)Yes
Selection sortO(n^2)O(n^2)O(n^2)O(1)No
Insertion sortO(n)O(n^2)O(n^2)O(1)Yes
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^2)O(log n)No
Heap sortO(n log n)O(n log n)O(n log n)O(1)No
Counting sortO(n + k)O(n + k)O(n + k)O(k)Yes

Stable means equal items keep their original order. In the counting sort row, k is the range of the values.

How to find the Big-O of your own code

  1. Count the loops. One loop over n items is O(n). A loop inside a loop is O(n^2).
  2. Halving gives log n. If each step cuts the problem in half, as in binary search, it is O(log n).
  3. Add steps that run one after another, then keep only the biggest term. O(n) + O(n^2) becomes O(n^2).
  4. Drop constants. 3n and 100n are both just O(n).

Frequently asked questions

What does Big-O notation mean?

Big-O describes how the running time or memory of an algorithm grows as the input size n gets larger. It ignores small details and focuses on the growth rate.

Which is faster, O(n log n) or O(n^2)?

O(n log n) grows much more slowly, so it is faster for large inputs. Sorting 1,000,000 items takes about 20 million steps with n log n, but about a trillion with n^2.

What is the difference between best, average and worst case?

They describe how the same algorithm behaves on lucky, typical and unlucky inputs. Exams usually ask for the worst case unless they say otherwise.

Test yourself with the data structures MCQs. More free tools: truth table generator · number base converter