Getting everything ready for you…

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

0s

Big-O Complexity Documentation

Time and space complexity of every common data structure and algorithm, and how to pick one from the constraints.

One page with the time and space complexity of every common data structure and algorithm, how to work out the complexity of your own code, and which complexity fits a problem's constraints. For the concepts from scratch read Time & Space Complexity (Big-O).

1. What Big-O Means

Big-O describes how the running time (or memory) of an algorithm grows as the input size n grows, ignoring constants and smaller terms.

  • 3n² + 5n + 20 → O(n²)
  • 2n + log n → O(n)
  • Constants are dropped: O(2n) = O(n), O(n/2) = O(n).
Notation Meaning
O (Big-O) upper bound — "grows no faster than" (usually the worst case)
Ω (Omega) lower bound — "grows at least as fast as"
Θ (Theta) tight bound — both

Best, average and worst case are different questions: quicksort is Θ(n log n) on average but O(n²) in the worst case.

2. Growth Rates Compared

Big-O Name n = 10 n = 1,000 n = 1,000,000 Example
O(1) constant 1 1 1 array index, hash lookup
O(log n) logarithmic 3 10 20 binary search
O(√n) square root 3 32 1,000 primality by trial division
O(n) linear 10 1,000 10⁶ one loop over the array
O(n log n) linearithmic 33 10⁴ 2 × 10⁷ merge sort, heap sort
O(n²) quadratic 100 10⁶ 10¹² ❌ nested loops, bubble sort
O(n³) cubic 1,000 10⁹ ❌ Floyd–Warshall, naive matrix multiply
O(2ⁿ) exponential 1,024 ❌ ❌ all subsets
O(n!) factorial 3.6 × 10⁶ ❌ ❌ all permutations

Order: 1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n!

3. Constraints → Expected Complexity

A typical judge does about 10⁸ simple operations per second. Use n from the problem to guess the intended solution:

n up to Acceptable Typical technique
10–12 O(n!), O(n · 2ⁿ) permutations, brute force
20–25 O(2ⁿ), O(n · 2ⁿ) subsets, bitmask DP, meet in the middle
100–500 O(n³) Floyd–Warshall, interval DP
1,000–5,000 O(n²) 2-D DP, nested loops
10⁵–10⁶ O(n log n) or O(n) sorting, heaps, binary search, two pointers, prefix sums
10⁷–10⁸ O(n) with small constant linear scan, sieve
10⁹–10¹⁸ O(log n) or O(1) binary search on answer, maths, fast power

4. Data Structure Operations

Structure Access Search Insert Delete Space
Array (static) O(1) O(n) O(n) O(n) O(n)
Dynamic array (vector, ArrayList, Python list) O(1) O(n) O(1) amortised at end, O(n) middle O(1) end, O(n) middle O(n)
Sorted array O(1) O(log n) O(n) O(n) O(n)
Singly linked list O(n) O(n) O(1) at head / known node O(1) at head O(n)
Doubly linked list O(n) O(n) O(1) at known node O(1) at known node O(n)
Stack / Queue / Deque O(n) O(n) O(1) O(1) O(n)
Hash table (unordered_map, HashMap, dict) — O(1) avg, O(n) worst O(1) avg O(1) avg O(n)
Balanced BST (map, set, TreeMap) O(log n) O(log n) O(log n) O(log n) O(n)
Unbalanced BST O(n) worst O(n) worst O(n) worst O(n) worst O(n)
Binary heap (priority_queue, heapq) top O(1) O(n) O(log n) pop O(log n) O(n)
Trie (key length L) — O(L) O(L) O(L) O(total chars × alphabet)
Segment tree / Fenwick tree — query O(log n) update O(log n) — O(n)
Disjoint set union (path compression + rank) — find ≈ O(α(n)) ≈ O(1) union ≈ O(1) — O(n)

Building a heap from an array with heapify is O(n), not O(n log n).

5. Sorting Algorithms

Algorithm Best Average Worst Space Stable Notes
Bubble sort O(n) O(n²) O(n²) O(1) ✅ best case with the "no swaps" check
Selection sort O(n²) O(n²) O(n²) O(1) ❌ fewest swaps (n − 1)
Insertion sort O(n) O(n²) O(n²) O(1) ✅ great for small / nearly sorted data
Merge sort O(n log n) O(n log n) O(n log n) O(n) ✅ linked lists, external sorting
Quick sort O(n log n) O(n log n) O(n²) O(log n) ❌ fastest in practice with random pivot
Heap sort O(n log n) O(n log n) O(n log n) O(1) ❌ in-place, guaranteed n log n
Counting sort O(n + k) O(n + k) O(n + k) O(k) ✅ small integer range k
Radix sort O(d(n + b)) O(d(n + b)) O(d(n + b)) O(n + b) ✅ d digits, base b
Bucket sort O(n + k) O(n + k) O(n²) O(n) ✅ uniformly distributed input
Tim sort (Python, Java objects) O(n) O(n log n) O(n log n) O(n) ✅ merge + insertion sort
Intro sort (C++ std::sort) O(n log n) O(n log n) O(n log n) O(log n) ❌ quick + heap + insertion

Comparison-based sorting can't beat Ω(n log n) in the worst case. More: Sorting Algorithms.

6. Searching & Graph Algorithms

Algorithm Time Space
Linear search O(n) O(1)
Binary search O(log n) O(1) iterative
BFS / DFS (adjacency list) O(V + E) O(V)
BFS / DFS (adjacency matrix) O(V²) O(V²)
Topological sort (Kahn / DFS) O(V + E) O(V)
Dijkstra (binary heap) O((V + E) log V) O(V)
Bellman–Ford O(V · E) O(V)
Floyd–Warshall O(V³) O(V²)
Prim (binary heap) O(E log V) O(V)
Kruskal (sort + DSU) O(E log E) O(V)
0-1 BFS O(V + E) O(V)
Kosaraju / Tarjan (SCC) O(V + E) O(V)

7. Other Classic Algorithms

Algorithm Time
Sieve of Eratosthenes O(n log log n)
GCD (Euclid) O(log min(a, b))
Fast exponentiation O(log n)
KMP / Z-algorithm string matching O(n + m)
Rabin–Karp O(n + m) average
Kadane (max subarray) O(n)
Sliding window / two pointers O(n)
Prefix sums: build / query O(n) / O(1)
LIS (patience sorting + binary search) O(n log n)
LCS / edit distance O(n · m)
0/1 knapsack O(n · W)
N-Queens backtracking O(n!)
Generate all subsets O(n · 2ⁿ)
Generate all permutations O(n · n!)

8. How to Analyse Your Code

Loops

for (int i = 0; i < n; i++) {}                 // O(n)
for (int i = 0; i < n; i++)
  for (int j = 0; j < n; j++) {}               // O(n²)
for (int i = 0; i < n; i++)
  for (int j = i; j < n; j++) {}               // n(n+1)/2 → O(n²)
for (int i = 1; i < n; i *= 2) {}              // O(log n)
for (int i = 0; i < n; i++)
  for (int j = 1; j < n; j *= 2) {}            // O(n log n)
for (int i = 1; i * i <= n; i++) {}            // O(√n)
for (int i = 1; i <= n; i++)
  for (int j = i; j <= n; j += i) {}           // n/1 + n/2 + … → O(n log n) (harmonic series)

Sequential blocks add (keep the largest): O(n) + O(n²) = O(n²). Nested blocks multiply.

Recursion — total work = (number of calls) × (work per call), or use a recurrence:

Recurrence Result Example
T(n) = T(n − 1) + O(1) O(n) factorial, linked-list recursion
T(n) = T(n − 1) + O(n) O(n²) selection sort recursive
T(n) = T(n/2) + O(1) O(log n) binary search
T(n) = 2T(n/2) + O(n) O(n log n) merge sort
T(n) = 2T(n/2) + O(1) O(n) tree traversal
T(n) = 2T(n − 1) + O(1) O(2ⁿ) naive Fibonacci, subsets

Master theorem for T(n) = a·T(n/b) + O(nᵈ):

  • d > log_b a → O(nᵈ)
  • d = log_b a → O(nᵈ log n)
  • d < log_b a → O(n^(log_b a))

Amortised analysis: a dynamic array occasionally doubles (O(n)), but n pushes cost O(n) total → O(1) amortised per push.

9. Space Complexity

Count extra memory the algorithm uses (input usually not counted):

  • A few variables → O(1).
  • A new array of size n / a hash map of n items → O(n).
  • A 2-D DP table n × m → O(n · m) (often reducible to O(m) with rolling rows).
  • Recursion uses the call stack: depth d → O(d) space (DFS on a skewed tree → O(n); balanced → O(log n)).

10. Cheat Sheet & References

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)

References