Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 225 · Analyzing Algorithms

Complexity Cheat Sheet

A one-page Big O cheat sheet for data structures, sorting, searching, graph algorithms and Python built-ins, plus how input limits tell you the target complexity.

This page collects the complexities you will use throughout the course in one place: growth classes, data structures, sorting and searching algorithms, graph algorithms, dynamic programming problems and the everyday Python built-ins. Bookmark it and come back whenever you need to check a bound or pick between two approaches. Every row links to the lesson where the idea is explained.

It also answers a practical question from the other direction: given the input limits of a problem, which complexity can you afford? That skill, reading n ≤ 10⁵ and thinking "so O(n log n)", is one of the quickest ways to find the right algorithm.

All bounds are worst case unless a row says "average" or "amortized". For what those words mean, see best, worst and average case and amortized analysis.

Growth classes, from fast to slow

Class Name Typical example
O(1) constant index a list, dict lookup (average)
O(log n) logarithmic binary search, heap push/pop
O(√n) square root trial division, jump search
O(n) linear one pass over a list
O(n log n) linearithmic merge sort, sorting in general
O(n²) quadratic all pairs, simple sorts
O(n³) cubic triple loops, Floyd-Warshall
O(2ⁿ) exponential all subsets, naive Fibonacci (about 1.62ⁿ)
O(n!) factorial all permutations

See Big O notation for the formal definitions and analyzing loops for how to find these in code. This code prints how fast each class grows:

Python How the classes grow

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

By n = 100 the exponential and factorial columns have 31 and 158 digits. No computer will ever finish those loops, which is why exponential algorithms are only for tiny inputs (or need pruning, see backtracking).

Data structures

Structure Access Search Insert Delete Notes
Array / Python list O(1) O(n) O(n); end: O(1) amortized O(n); end: O(1) contiguous memory
Singly linked list O(n) O(n) O(1) at head or after a known node O(1) if you hold the previous node no random access
Doubly linked list O(n) O(n) O(1) at either end O(1) given the node extra pointer per node
Stack top O(1) O(n) push O(1) pop O(1) LIFO
Queue / deque ends O(1) O(n) O(1) at the ends O(1) at the ends use collections.deque
Hash table n/a O(1) average, O(n) worst O(1) average O(1) average needs good hashing
Binary search tree O(h) O(h) O(h) O(h) h = O(log n) if balanced, O(n) if skewed
Balanced BST (AVL) O(log n) O(log n) O(log n) O(log n) height guaranteed
Binary heap min/max O(1) O(n) O(log n) O(log n) top build from list O(n)
Trie n/a O(L) O(L) O(L) L = length of the key
Union-find n/a α(n) per find α(n) per union n/a amortized, nearly constant
Segment tree n/a query O(log n) update O(log n) n/a build O(n), space O(n)
Fenwick tree n/a prefix query O(log n) update O(log n) n/a build O(n), space O(n)
Sparse table n/a query O(1) static static build O(n log n), space O(n log n)

Sorting algorithms

Algorithm Best Average Worst Extra space Stable?
Bubble sort O(n) with early exit O(n²) O(n²) O(1) yes
Selection sort O(n²) O(n²) O(n²) O(1) no
Insertion sort O(n) O(n²) O(n²) O(1) yes
Merge sort O(n log n) O(n log n) O(n log n) O(n) yes
Quick sort O(n log n) O(n log n) O(n²) O(log n) stack no
Heap sort O(n log n) O(n log n) O(n log n) O(1) no
Counting sort O(n + k) O(n + k) O(n + k) O(k) yes
Radix sort O(d(n + k)) O(d(n + k)) O(d(n + k)) O(n + k) yes
Timsort (Python) O(n) O(n log n) O(n log n) O(n) yes

No sort that works by comparing items can beat O(n log n) in the worst case. Counting and radix sort avoid comparisons and exploit the range of the keys instead.

Searching and strings

Algorithm Time Space Needs
Linear search O(n) O(1) nothing
Binary search O(log n) O(1) sorted data
Exponential search O(log n) O(1) sorted data, unbounded or unknown size
Interpolation search O(log log n) average, O(n) worst O(1) sorted, evenly spread values
Naive pattern matching O(n × m) O(1) n = text, m = pattern
KMP O(n + m) O(m) the failure table
Rabin-Karp O(n + m) average, O(n × m) worst O(1) rolling hash
Z-algorithm O(n + m) O(n + m) Z array
Manacher O(n) O(n) all palindromes

Graph algorithms

V is the number of vertices and E the number of edges.

Algorithm Time Space Use
BFS O(V + E) O(V) shortest path by edge count
DFS O(V + E) O(V) components, cycles, ordering
Topological sort O(V + E) O(V) DAG ordering
Dijkstra (heap) O((V + E) log V) O(V) non-negative weights
Bellman-Ford O(V × E) O(V) negative weights
Floyd-Warshall O(V³) O(V²) all pairs
Kruskal O(E log E) O(V) minimum spanning tree
Prim (heap) O(E log V) O(V) minimum spanning tree
Strongly connected components O(V + E) O(V) directed cycles groups

Dynamic programming and recursion

Problem Time Space (optimized)
Fibonacci, 1D DP O(n) O(1)
0/1 knapsack (n items, capacity W) O(n × W) O(W)
Coin change (amount A, k coins) O(A × k) O(A)
LCS / edit distance O(n × m) O(min(n, m))
LIS O(n log n) with binary search O(n)
Bitmask DP (travelling salesman) O(2ⁿ × n²) O(2ⁿ × n)
All subsets O(2ⁿ × n) O(n)
All permutations O(n! × n) O(n)

For the solution of recursive costs, see recurrences and the master theorem.

Python built-ins

These are the costs of the structures you will actually use. Memorize the O(n) traps: x in list, list.insert(0, x), list.pop(0), and string + in loops.

Operation Cost
list: lst[i], len, append, pop() O(1) (append amortized)
list: insert(i, x), pop(i), remove(x), x in lst, index, count O(n)
list: lst[a:b], copy, reverse, min, max, sum O(k) for the slice, O(n) for the others
list.sort(), sorted(x) O(n log n); O(n) when already sorted; sorted() needs O(n) space
dict / set: get, set, delete, in O(1) average, O(n) worst
set operations: a & b, a | b, a - b about O(len(a) + len(b))
collections.deque: append, appendleft, pop, popleft O(1)
deque[i] in the middle, x in deque O(n)
heapq.heappush, heappop O(log n)
heapq.heapify O(n)
heapq.nsmallest(k, data) about O(n log k)
bisect.bisect_left O(log n)
bisect.insort O(n) (the search is O(log n), but inserting shifts items)
str: s[i], len O(1)
str: s + t, s[a:b], split, "".join(parts) O(length of the result)
collections.Counter(data) O(n)
functools.cache lookup O(1) average per call

Here are some of those in action, all with output that is independent of speed:

Python Built-ins in practice

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

From input limits to the target complexity

Judges and interviewers state limits for a reason. A rough rule: a computer does about 10⁸ simple operations in a few seconds in a fast language, and Python is considerably slower, so aim lower (roughly 10⁶ to 10⁷ steps) when you write Python. That budget tells you which complexity is affordable for a given n.

Limit on n Complexity you can afford Typical technique
n ≤ 10 O(n!) permutations, brute-force backtracking
n ≤ 20 O(2ⁿ) subsets, bitmask DP, meet in the middle
n ≤ 500 O(n³) Floyd-Warshall, triple-loop DP
n ≤ 5,000 O(n²) nested loops, 2D DP tables
n ≤ 10⁵ to 10⁶ O(n log n) sorting, heaps, binary search, segment trees
n ≤ 10⁷ O(n) hashing, two pointers, sliding window, prefix sums
n up to 10¹⁸ O(log n) or O(1) binary search, fast exponentiation, math

The next program turns this into numbers: for each complexity it finds the biggest n that fits within a budget of 10⁸ operations.

Python Largest n for a budget of operations

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The results show the gap: factorial and exponential algorithms survive only for tiny inputs, quadratic ones reach about ten thousand, and linearithmic ones reach millions. A single step down the ladder, from n² to n log n, multiplies the input you can handle by hundreds.

Finally, here is that table as code. Use it as a mental checklist:

Python Constraint to complexity advisor

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Limits are hints, not laws. Constants matter (a tight O(n²) loop on n = 10⁴ may be fine, a heavy one on n = 3000 may not), and in Python the budget shrinks by one or two orders of magnitude. When in doubt, count steps like you learned in analyzing loops.

Common mistakes with complexity tables

  • Reading average as worst. Hash tables and quicksort have bad worst cases that adversarial input can trigger.
  • Forgetting hidden costs. list.insert, slicing and string concatenation look like one line but are O(n).
  • Ignoring space. Merge sort, memoization and BFS all spend extra memory (see space complexity).
  • Mixing V and E. Dense graphs have E close to V², which changes which algorithm wins.
  • Trusting a table over the context. If n is 50, an "inefficient" O(n²) solution is the right one.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. A problem says n <= 100000. Which complexity should you aim for in the solution?

    n squared would be 10 billion steps, far over the budget. O(n log n) is about 1.7 million steps and O(n) is even better.
  2. 2. Which Python operation is O(n) and often surprises beginners?

    Inserting at the front shifts every other element one place to the right. Use a deque if you need fast operations at the front.
  3. 3. Which sorting algorithm has an O(n log n) worst case and O(1) extra space?

    Merge sort needs O(n) extra space, quick sort can degrade to O(n²), and counting sort needs O(k) extra. Heap sort sorts in place with a guaranteed O(n log n).
  4. 4. What is the time complexity of Dijkstra's algorithm with a binary heap?

    Each edge may cause a heap push or update costing O(log V), plus V pops, giving O((V + E) log V).
  5. 5. Why is dict lookup described as O(1) average but O(n) worst case?

    With good hashing collisions are rare, so lookups take constant time on average. In the worst case (many collisions) they degrade toward linear.

Summary

  • Learn the growth ladder: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!).
  • Know the costs of the structures you pick: arrays are fast to index, hash tables to look up, heaps to find the minimum, balanced trees to keep things ordered.
  • Comparison sorts cannot beat O(n log n); counting and radix sort exploit key ranges.
  • Graph algorithm costs are expressed in V and E; BFS and DFS are O(V + E), Dijkstra needs a heap, Floyd-Warshall is cubic.
  • In Python, watch for O(n) traps: x in list, insert(0, x), pop(0), and string concatenation in loops.
  • Use input limits to choose the target complexity: n up to 10⁵ means O(n log n), up to 5,000 means O(n²), up to 20 allows O(2ⁿ).

That completes the chapter on analyzing algorithms. Time to put the ideas to work.

Next: Arrays and Python Lists