Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Big-O Complexity Cheat Sheet

Growth order

// fastest → slowest
O(1) < O(log n) < O(sqrt n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)
// about 1e8 simple operations per second

Pick by constraint

n <= 12        → O(n!)
n <= 25        → O(2^n)
n <= 500       → O(n^3)
n <= 5000      → O(n^2)
n <= 1e6       → O(n log n)
n <= 1e8       → O(n)
n >= 1e9       → O(log n) or O(1)

Data structures

array access O(1); search O(n)
hash map get/put O(1) avg, O(n) worst
balanced BST / map / set: O(log n) everything
heap push/pop O(log n), top O(1), heapify O(n)
stack/queue push/pop O(1)
linked list insert at known node O(1), search O(n)

Algorithms

binary search O(log n); sort O(n log n)
BFS/DFS O(V + E); Dijkstra O((V + E) log V)
Floyd–Warshall O(V^3); Bellman–Ford O(V * E)
subsets O(2^n); permutations O(n!)
merge sort space O(n); quick sort worst O(n^2)

Loop patterns

for (i = 1; i < n; i *= 2)          // O(log n)
for (i = 1; i * i <= n; i++)        // O(sqrt n)
for (i...n) for (j...n)             // O(n^2)
for (i...n) for (j = 1; j < n; j *= 2)  // O(n log n)

Full Big-O Complexity documentation