Big-O Cheat Sheet

The time and space complexity of 96 data structures and algorithms on one page. Click any name to watch it run as an interactive 3D model.

What Big-O notation means

Big-O describes how the work an algorithm does grows as its input grows. It ignores constant factors and small inputs and keeps only the part that dominates for large n. An O(n log n) sort will always beat an O(n²) sort once the list is long enough, whatever computer runs them.

Big-O	Name	In words	Steps for n = 1,000,000	Example
`O(1)`	Constant	Same work no matter how big the input is.	1	Array access by index, stack push/pop
`O(log n)`	Logarithmic	Halves the problem each step.	≈ 20	Binary search, balanced-tree lookup
`O(n)`	Linear	Looks at every item once.	1,000,000	Linear search, one pass over an array
`O(n log n)`	Linearithmic	The best possible for comparison sorting.	≈ 20,000,000	Merge sort, heap sort
`O(n²)`	Quadratic	Compares every pair of items.	10¹²	Bubble sort, insertion sort (worst case)
`O(2ⁿ)`	Exponential	Doubles with every extra item.	more than atoms in the universe	Trying every subset by brute force

Jump to:Data Structures · Design & Analysis of Algorithms · AI & Machine Learning · Operating Systems · Database Management Systems · Computer Networks · Theory of Computation · Computer Organization & Architecture

Data Structures

Topic	Case / operation	Time	Notes
Arrays & Strings	Access a[i]	`O(1)`	Address is calculated directly.
	Search (unsorted)	`O(n)`	Check elements one by one.
	Insert / delete at the end	`O(1)`	Nothing has to move.
	Insert / delete at index i	`O(n)`	Everything after i shifts.
	Reverse / palindrome (two pointers)	`O(n)`	n/2 steps, no extra array.
	Extra space	`O(n)`
Stack	push(x)	`O(1)`	Only the top position changes.
	pop()	`O(1)`	Only the top position changes.
	peek()	`O(1)`	Reads one element.
	search(x)	`O(n)`	You may have to pop through every element.
	Extra space	`O(n)`
Queue	enqueue(x)	`O(1)`	Write at the rear index.
	dequeue() — circular array	`O(1)`	Just move the front index.
	dequeue() — shifting array	`O(n)`	Every remaining element moves one place.
	peek()	`O(1)`	Read the front element.
	Extra space	`O(n)`
Linked List	Insert at head	`O(1)`	Only two pointers change.
	Insert at tail (no tail pointer)	`O(n)`	Must walk to the last node.
	Insert / delete after a known node	`O(1)`	Just re-wire pointers.
	Search / access by index	`O(n)`	No random access — walk from the head.
	Reverse	`O(n)`	One pass, flipping each arrow.
	Extra space	`O(n)`
Binary Search Tree (BST)	Search / insert / delete — balanced tree	`O(log n)`	Each step goes one level down; a balanced tree has about log₂ n levels.
	Search / insert / delete — worst case	`O(n)`	Inserting sorted data makes the tree a straight line.
	Traversal (any order)	`O(n)`	Every node is visited exactly once.
	Extra space	`O(n)`
Binary Heap & Priority Queue	peek (get min)	`O(1)`	The minimum is always at index 0.
	insert	`O(log n)`	Bubble up at most one level per swap.
	extractMin	`O(log n)`	Sift down at most one level per swap.
	build heap from n items	`O(n)`	Bottom-up heapify (a surprising but proven result).
	heap sort	`O(n log n)`	n extractions of O(log n) each.
	Extra space	`O(n)`
Hash Table	Insert / search / delete — average	`O(1)`	Hash straight to the right bucket.
	Insert / search / delete — worst case	`O(n)`	All keys collide into one bucket.
	Resize (rehash) when too full	`O(n)`	Rare, so still O(1) amortised.
	Extra space	`O(n)`
Trie (Prefix Tree)	Insert a word of length L	`O(L)`	One step per letter — independent of how many words are stored.
	Search a word of length L	`O(L)`	Same walk as insert.
	Prefix search (autocomplete)	`O(L + k)`	Walk the prefix, then collect k results.
	Extra space	`O(total letters × alphabet)`
AVL Tree	Search	`O(log n)`	Height is always about 1.44 log₂ n.
	Insert (with rebalancing)	`O(log n)`	At most one single or double rotation.
	Delete (with rebalancing)	`O(log n)`	May rotate at several levels.
	One rotation	`O(1)`	Only three pointers change.
	Extra space	`O(n)`
Red-Black Tree	Search	`O(log n)`	Height is at most 2 · log₂(n + 1).
	Insert	`O(log n)`	Recolourings go up the tree; at most 2 rotations.
	Delete	`O(log n)`	At most 3 rotations.
	Extra space	`O(n)`
Segment Tree	Build	`O(n)`	Each of the ~2n nodes is computed once.
	Range query	`O(log n)`	At most ~4 nodes per level are visited.
	Point update	`O(log n)`	One node per level, leaf to root.
	Naive array (for comparison)	`O(n) query / O(1) update`	Prefix sums are the opposite trade-off.
	Extra space	`O(n)`
Fenwick Tree (Binary Indexed Tree)	Prefix sum	`O(log n)`	One step per 1 bit in i.
	Point update	`O(log n)`	Climb to every cell whose range contains i.
	Range sum	`O(log n)`	Two prefix sums.
	Build	`O(n log n)`	O(n) with a clever single pass.
	Extra space	`O(n)`
Disjoint Set (Union–Find)	Find / Union (rank + path compression)	`O(α(n)) ≈ O(1)`	α is the inverse Ackermann function, ≤ 4 for any practical n.
	Find / Union (naive)	`O(n)`	Trees can degenerate into chains.
	Make set	`O(1)`	parent[x] = x
	Extra space	`O(n)`
Graph Representation	Memory — matrix	`O(V²)`	One cell per pair of vertices.
	Memory — list	`O(V + E)`	One entry per edge end.
	Is there an edge u–v? — matrix / list	`O(1) / O(deg u)`	Direct cell lookup vs scanning a list.
	All neighbours of u — matrix / list	`O(V) / O(deg u)`	Scan a whole row vs walk a short list.
	Extra space	`O(V²) or O(V + E)`
Monotonic Stack (Next Greater Element)	Whole array	`O(n)`	Each index is pushed once and popped at most once.
	Brute force (compare every pair)	`O(n²)`	Shown for comparison.
	Extra space	`O(n) for the stack`
Bloom Filter	Add / check	`O(k)`	k hash computations, independent of how many items are stored.
	False positive rate	`≈ (1 − e^(−kn/m))^k`	n items, m bits, k hash functions.
	Extra space	`m bits (about 10 bits per item for a 1% error rate)`

Design & Analysis of Algorithms

Topic	Case / operation	Time	Notes
Binary Search	Best case	`O(1)`	The target is exactly in the middle.
	Average / worst case	`O(log n)`	The range halves every step.
	Linear search (for comparison)	`O(n)`	Checks elements one by one.
	Extra space	`O(1)`
Bubble Sort	Best case (already sorted)	`O(n)`	One pass with no swaps, then stop early.
	Average case	`O(n²)`	About n²/4 swaps.
	Worst case (reversed)	`O(n²)`	n(n−1)/2 comparisons and swaps.
	Extra space	`O(1)`
Selection Sort	Best case (already sorted)	`O(n²)`	It still scans the whole unsorted part every pass.
	Average case	`O(n²)`	Exactly n(n−1)/2 comparisons.
	Worst case	`O(n²)`	Same comparisons as the best case.
	Swaps	`O(n)`	At most one per pass, n − 1 in total.
	Extra space	`O(1)`
Insertion Sort	Best case (already sorted)	`O(n)`	One comparison per element, no shifts.
	Average case	`O(n²)`	About n²/4 shifts.
	Worst case (reversed)	`O(n²)`	Every key shifts past all sorted elements.
	Extra space	`O(1)`
Merge Sort	Best case	`O(n log n)`	It always splits and merges fully.
	Average case	`O(n log n)`	log₂ n levels × n work per level.
	Worst case	`O(n log n)`	Guaranteed — no bad inputs.
	Extra space	`O(n)`
Quick Sort	Best case	`O(n log n)`	The pivot splits the array into two equal halves.
	Average case	`O(n log n)`	Random data gives reasonably balanced splits.
	Worst case	`O(n²)`	The pivot is always the smallest or largest (e.g. sorted input with a last-element pivot).
	Extra space	`O(log n)`
Heap Sort	Best case	`O(n log n)`	Every extraction still sifts down.
	Average case	`O(n log n)`
	Worst case	`O(n log n)`	Guaranteed — unlike quick sort.
	Build heap	`O(n)`	Bottom-up heapify.
	Extra space	`O(1)`
Counting Sort & Radix Sort	Counting sort (values 0 … k)	`O(n + k)`	One pass over the input, one over the counts.
	Radix sort (d digits, base b)	`O(d · (n + b))`	d stable counting sorts, one per digit.
	Any comparison sort	`Ω(n log n)`	The limit these algorithms avoid.
	Extra space	`O(n + k)`
Graph Traversal — BFS & DFS	BFS / DFS with an adjacency list	`O(V + E)`	Every vertex is visited once and every edge checked at most twice.
	BFS / DFS with an adjacency matrix	`O(V²)`	Finding neighbours means scanning a whole row.
	Extra space	`O(V)`
Topological Sort	Kahn's algorithm	`O(V + E)`	Every node enters the queue once; every edge is removed once.
	DFS method	`O(V + E)`	Every node is visited once; every edge is followed once.
	Detecting a cycle	`O(V + E)`	Comes for free with either method.
	Extra space	`O(V)`
Dijkstra's Shortest Path	Simple array version	`O(V²)`	Scan all vertices to find the minimum each round.
	Binary heap (priority queue)	`O((V + E) log V)`	The usual choice for sparse graphs.
	Fibonacci heap	`O(E + V log V)`	Best in theory, rarely used in practice.
	Extra space	`O(V)`
Bellman–Ford Algorithm	Up to V − 1 passes over all edges	`O(V × E)`	Each pass relaxes every edge once.
	Negative-cycle check	`O(E)`	One extra pass.
	Best case (early stop)	`O(E)`	When a pass changes nothing, every distance is final.
	Dijkstra, for comparison	`O((V + E) log V)`	Faster, but needs non-negative weights.
	Extra space	`O(V)`
Minimum Spanning Tree — Prim & Kruskal	Kruskal (sort + union-find)	`O(E log E)`	Sorting the edges dominates.
	Prim (binary heap)	`O(E log V)`
	Prim (adjacency matrix, no heap)	`O(V²)`	Good for dense graphs.
	Extra space	`O(V + E)`
Floyd–Warshall (All-Pairs Shortest Paths)	Time	`O(V³)`	Three nested loops over the vertices.
	Dijkstra from every vertex (for comparison)	`O(V · E log V)`	Faster on sparse graphs, but no negative edges.
	Extra space	`O(V²)`
0/1 Knapsack (Dynamic Programming)	Fill the table	`O(n × W)`	One constant-time decision per cell.
	Trace back the items	`O(n)`
	Brute force (try every subset)	`O(2ⁿ)`	Hopeless beyond ~30 items.
	Extra space	`O(n × W)`
Longest Common Subsequence (LCS)	Fill the table	`O(m × n)`	One cell per pair of prefixes.
	Trace back	`O(m + n)`
	Brute force (all subsequences)	`O(2ᵐ × n)`
	Extra space	`O(m × n)`
Matrix Chain Multiplication	Filling the table	`O(n³)`	O(n²) cells, each trying up to n splits.
	Reading the brackets	`O(n)`	Follow s[i][j] recursively.
	Trying every bracketing	`exponential (Catalan numbers)`	Why brute force is hopeless.
	Extra space	`O(n²)`
Huffman Coding	Build the tree (k distinct characters)	`O(k log k)`	k − 1 merges, each with heap operations.
	Count frequencies (text of length n)	`O(n)`
	Encode / decode	`O(n · code length)`
	Extra space	`O(k)`
KMP String Matching	Building the LPS table	`O(m)`	m = length of the pattern.
	Searching the text	`O(n)`	At most 2n comparisons; i never moves back.
	Naive search, worst case	`O(n · m)`	Re-reads text after every mismatch.
	Extra space	`O(m) for the LPS table`
N-Queens (Backtracking)	Backtracking (first solution)	`O(N!) worst case`	Pruning makes it far faster in practice.
	Brute force (any N squares)	`O(C(N², N))`	For N = 8 that's over 4 billion placements.
	safe() check with sets	`O(1)`	Track used columns and diagonals.
	Extra space	`O(N)`
Edit Distance (Levenshtein)	Fill the table	`O(m × n)`	Each of the (m+1)(n+1) cells looks at three neighbours.
	Memory	`O(m × n)`	Can be reduced to O(min(m, n)) if only the distance is needed.
	Extra space	`O(m × n) table`
Activity Selection (Greedy)	Sorting by finish time	`O(n log n)`	Skipped if the input is already sorted.
	Greedy scan	`O(n)`	One pass, comparing start time with the last finish.
	Extra space	`O(1) extra (plus the output)`

AI & Machine Learning

Topic	Case / operation	Time	Notes
Gradient Descent	One step (n parameters)	`O(n)`	Compute the gradient and update every parameter.
	One step on a dataset of m examples (batch)	`O(m · n)`	The gradient sums over every training example.
	Stochastic / mini-batch step	`O(b · n)`	Uses only b examples per step — much cheaper.
	Extra space	`O(n)`
Linear Regression	Prediction for one input	`O(d)`	d = number of features.
	One gradient descent step	`O(n · d)`	Uses every training example.
	Normal equation (exact)	`O(n · d² + d³)`	Matrix inversion — slow for many features.
	Extra space	`O(d)`
Logistic Regression	Prediction	`O(d)`	One weighted sum and a sigmoid.
	One training step	`O(n · d)`
	Extra space	`O(d)`
Support Vector Machine (SVM)	Training (kernel SVM, n points)	`O(n²) to O(n³)`	Solving a quadratic optimisation problem.
	Training (linear SVM, modern solvers)	`≈ O(n · d)`	Coordinate descent and similar methods.
	Prediction	`O(s · d)`	s support vectors, d features (O(d) for a linear SVM).
	Extra space	`O(s · d) for the model`
Neural Network (Forward Pass)	Forward pass (one input)	`O(total weights)`	Every weight is used once — one multiply and one add.
	Dense layer with n inputs and m neurons	`O(n · m)`	This is a matrix–vector multiplication.
	Extra space	`O(total weights)`
Convolutional Neural Network (CNN)	One convolution (H×W image, k×k kernel)	`O(H · W · k²)`
	Parameters of a conv layer	`k × k × channels_in × channels_out`	Tiny compared with a fully connected layer.
	Max-pooling 2×2	`O(H · W)`
	Extra space	`O(H · W) per feature map`
Transformers & Self-Attention	Attention over n tokens (d dimensions)	`O(n² · d)`	Every token is compared with every other token.
	Memory for the attention table	`O(n²)`	Why very long contexts are expensive.
	Sequential steps per layer	`O(1)`	All tokens are processed at once (an RNN needs n steps).
	Extra space	`O(n² + n · d)`
K-Nearest Neighbours (KNN)	Training	`O(1)`	Just store the data ("lazy learning").
	Prediction (brute force)	`O(n · d)`	Distance to every training point.
	Prediction with a k-d tree (low d)	`about O(log n)`
	Extra space	`O(n · d)`
Naive Bayes Classifier	Training (n messages, total length L)	`O(L)`	Just count words, one pass.
	Classifying a message of m words	`O(m · k)`	k classes, one lookup per word and class.
	Model size	`O(V · k)`	One probability per word per class.
	Extra space	`O(V · k)`
Decision Tree	Prediction	`O(depth)`	Answer one question per level.
	Training (n points, d features)	`O(d · n log n · depth)`	Sort values to try every threshold.
	Extra space	`O(number of nodes)`
K-Means Clustering	One iteration	`O(n · k · d)`	n points × k centroids × d features distances.
	Whole algorithm	`O(i · n · k · d)`	i iterations — usually small (tens).
	Extra space	`O(n · d + k · d)`
Principal Component Analysis (PCA)	Covariance matrix (n points, d features)	`O(n · d²)`
	Eigen-decomposition	`O(d³)`
	Projecting the data	`O(n · d · k)`
	Extra space	`O(d²)`
A* Search	Worst case (grid with V cells)	`O(V log V)`	With a priority queue for the open set.
	With a perfect heuristic	`O(path length)`	It walks straight to the goal.
	Extra space	`O(V)`
Minimax & Alpha–Beta Pruning	Minimax (branching b, depth d)	`O(bᵈ)`	Visits every leaf.
	Alpha-beta, best move ordering	`O(b^(d/2))`	Can search twice as deep in the same time.
	Alpha-beta, worst ordering	`O(bᵈ)`
	Extra space	`O(b · d)`
Q-Learning (Reinforcement Learning)	One Q-learning update	`O(\|A\|)`	Look up max over the actions of the next state.
	Q-table size	`O(\|S\| · \|A\|)`	One value per state–action pair (here 25 × 4).
	Episodes to converge	`grows with the state space`	Every pair must be tried many times.
	Extra space	`O(\|S\| · \|A\|)`
Perceptron	One prediction	`O(d)`	A dot product over d features.
	One epoch	`O(n · d)`	n points, d features each.
	Mistakes before convergence	`≤ (R/γ)²`	Novikoff's bound for separable data with margin γ and radius R.
	Extra space	`O(d) weights`
Genetic Algorithm	One generation	`O(P · L)`	P individuals of length L: evaluate, select, cross over, mutate.
	Generations needed	`problem dependent`	No guarantee of finding the optimum, but usually far fewer evaluations than brute force.
	Extra space	`O(P · L)`

Operating Systems

Topic	Case / operation	Time	Notes
CPU Scheduling (FCFS, SJF, SRTF, Round Robin, Priority)	FCFS selection	`O(1)`	Take the front of a queue.
	SJF / SRTF / Priority selection	`O(log n)`	Using a min-heap of ready processes.
	Round Robin selection	`O(1)`	Circular queue.
	Extra space	`O(n)`
Process Synchronization (Semaphores & Mutex)	wait() / signal() on a semaphore	`O(1)`	Plus the cost of sleeping/waking a process.
	Busy-waiting spinlock	`Wastes CPU while waiting`	OK only for very short critical sections.
	Extra space	`O(1) per semaphore`
Deadlock & Banker's Algorithm	Safety algorithm (n processes, m resource types)	`O(m · n²)`	Up to n passes over n processes.
	Resource request check	`O(m · n²)`	Runs the safety algorithm.
	Extra space	`O(m · n)`
Memory Allocation (First, Next, Best & Worst Fit)	First fit	`O(h)`	Stops at the first hole that fits (h = number of holes).
	Next fit	`O(h)`	Like first fit, but starts where the last search ended.
	Best fit / Worst fit	`O(h)`	Must look at every hole (O(log h) with a sorted tree of holes).
	Extra space	`O(h) to keep the list of holes`
Paging & Address Translation (TLB)	TLB hit	`t + m`	TLB lookup, then the actual memory access.
	TLB miss (page table in memory)	`t + 2m`	Extra memory access to read the page table.
	Effective access time	`h(t + m) + (1 − h)(t + 2m)`	h = TLB hit ratio.
	Page fault	`milliseconds`	The page must come from disk — about 100,000× slower.
Paging & Page Replacement (FIFO, LRU, Optimal)	FIFO per reference	`O(1)`	A queue of loaded pages.
	LRU per reference	`O(1)`	Hash map + doubly linked list.
	Optimal per reference	`O(n)`	Must look into the future — not implementable in practice.
	Extra space	`O(frames)`
Disk Scheduling (FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK)	FCFS	`O(n)`	Serve the requests in arrival order.
	SSTF	`O(n²)`	n times, search the pending requests for the nearest one.
	SCAN, C-SCAN, LOOK, C-LOOK	`O(n log n)`	Sort the requests once, then sweep across them.
	Head movement of one SCAN sweep	`≤ 2 × disk size`	Out to one edge and back across the disk.
	Extra space	`O(n)`
Dining Philosophers Problem	Naive solution	`can deadlock`	Circular wait is possible when everyone holds one fork.
	Resource ordering	`deadlock-free`	Breaks circular wait; starvation is still possible with an unfair scheduler.
	Waiter (n − 1 seats)	`deadlock-free`	At least one philosopher can always get both forks.
	Extra space	`One lock or semaphore per fork`
File Allocation Methods	Read block k (contiguous)	`O(1)`	address = start + k
	Read block k (linked)	`O(k)`	Follow k pointers, one disk read each.
	Read block k (indexed)	`O(1)`	Index block first, then the data block (2 reads).
	Extra space	`Pointers or an index per file`

Database Management Systems

Topic	Case / operation	Time	Notes
SQL Joins (INNER, LEFT, RIGHT, FULL)	Nested loop join	`O(n × m)`	Compare every pair of rows.
	Hash join	`O(n + m)`	Build a hash table on one table.
	Sort-merge join	`O(n log n + m log m)`
	Extra space	`O(n + m) for hash join`
Functional Dependencies, Closure & Candidate Keys	Closure X⁺ (n attributes, f dependencies)	`O(n · f)`	Each pass adds at least one attribute, at most n passes.
	Finding all candidate keys	`O(2ⁿ · n · f)`	Worst case tries every subset; the core and superset pruning help a lot.
	Checking if X is a superkey	`O(n · f)`	Just compare X⁺ with all attributes.
Normalization (1NF, 2NF, 3NF)	Effect on reads	`More joins`	Data is split across tables.
Normalization (1NF, 2NF, 3NF)	Effect on writes	`Fewer updates`	Each fact is stored once.
Transactions & ACID	Write-ahead logging per update	`O(1)`	Append a log record before changing data.
Transactions & ACID	Recovery after a crash	`O(log size)`	Scan the log to redo / undo.
Conflict Serializability	Finding all conflicting pairs (n operations)	`O(n²)`	Compare every pair once.
	Cycle check / serial order (t transactions)	`O(t + e)`	DFS or a topological sort of the graph.
	Testing view serializability	`NP-complete`	Why databases use the conflict test instead.
B+ Tree Indexing	Search	`O(log n)`	One node (disk block) per level.
	Insert / delete	`O(log n)`	Splits only travel up one path.
	Range query returning k keys	`O(log n + k)`	Walk the leaf chain.
	Extra space	`O(n)`
Relational Algebra (Select and Project)	Selection σ	`O(n)`	One test per row, or O(log n) with an index.
	Projection π	`O(n)`	Plus duplicate removal, which needs hashing or sorting.
	Duplicate elimination	`O(n) hashing, O(n log n) sorting`
	Extra space	`O(n) for the result`
Deadlock Detection (Wait-For Graph)	Cycle detection (DFS)	`O(V + E)`	V transactions and E waits-for edges.
	Deadlock prevention (wait-die)	`O(1) per lock request`	Compare transaction timestamps; no graph needed.
	Extra space	`O(V + E) for the graph`

Computer Networks

Topic	Case / operation	Time	Notes
OSI & TCP/IP Layers	OSI layers	`7`	Reference model for teaching and troubleshooting.
OSI & TCP/IP Layers	TCP/IP layers	`4`	The model the internet actually uses.
CRC (Cyclic Redundancy Check)	Computing the CRC bit by bit	`O(n · r)`	n data bits, an r-bit remainder.
	Table-driven CRC (one byte at a time)	`O(n / 8) lookups`	How network cards and libraries really do it.
	Extra bits sent	`r`	The degree of the generator.
	Bursts of errors always caught	`length ≤ r`	Longer bursts slip through with probability about 2^−r.
Hamming Code	Parity bits for m data bits	`r with 2^r ≥ m + r + 1`	About log₂ m extra bits.
	Encoding / checking	`O(n log n)`	r groups, each up to n bits (O(n) with XOR tricks).
	Errors corrected	`1 bit`	Add one overall parity bit (SECDED) to also detect 2-bit errors.
Sliding Window Protocol	Max frames in flight	`N (window size)`
	Retransmissions after one loss — Go-Back-N	`up to N`	The lost frame and everything after it.
	Retransmissions after one loss — Selective Repeat	`1`	Only the lost frame.
	Extra space	`Receiver buffer of N frames (Selective Repeat)`
Subnetting & CIDR (IPv4)	Addresses in a /n network	`2^(32 − n)`	Every extra host bit doubles the size.
	Usable hosts in a /n network	`2^(32 − n) − 2`	The network and broadcast addresses are reserved.
	Find network or broadcast address	`O(1)`	One bitwise AND (or OR) on 32 bits.
	Subnets after borrowing b bits	`2^b`	Each one has 2^(32 − n − b) addresses.
Routing Algorithms (Distance Vector)	One round (V routers, E links)	`O(V · E)`	Every router combines its neighbours' vectors.
	Rounds to converge	`≤ V − 1`	The longest shortest path in hops.
	Extra space	`O(V) per router`
TCP 3-Way Handshake	Messages to open a connection	`3`	SYN, SYN-ACK, ACK.
	Messages to close	`4`	FIN, ACK, FIN, ACK.
	Delay before data can flow	`1 round-trip time`
TCP Congestion Control	Slow start	`doubles per RTT`	Exponential growth until cwnd reaches ssthresh.
	Congestion avoidance	`+1 MSS per RTT`	Additive increase.
	After a loss	`cwnd / 2`	Multiplicative decrease (to 1 after a timeout).
	Rounds to reach a window of W from 1	`about log₂ W`	Thanks to slow start.
Token Bucket (Traffic Shaping)	Per packet	`O(1)`	Check and decrement a counter.
	Maximum burst	`bucket size`	A full bucket lets that many packets go at once.
	Long-run average rate	`token rate`	Never more than the tokens added per tick.
	Extra space	`O(1) — one counter and a timestamp`
DNS Resolution	Cold lookup	`8 messages`	Browser → resolver, then 3 query/reply pairs to root, TLD and authoritative servers, then the reply.
	Cached lookup	`2 messages`	The resolver answers from its cache until the TTL expires.
	Extra space	`One cache entry per name and record type`

Theory of Computation

Topic	Case / operation	Time	Notes
DFA & NFA (Finite Automata)	Run a DFA on a string of length n	`O(n)`	One transition per symbol.
	Simulate an NFA with k states	`O(n · k²)`	Track the set of possible states.
	Convert NFA → DFA (subset construction)	`up to O(2ᵏ) states`
	Extra space	`O(1) for a DFA, O(k) for an NFA`
DFA Minimization	Removing unreachable states	`O(n · \|Σ\|)`	One BFS from the start state.
	Partition refinement (Moore)	`O(n² · \|Σ\|)`	At most n rounds, each looks at every transition.
	Hopcroft's algorithm	`O(n · \|Σ\| · log n)`	The fastest known method.
	Extra space	`O(n)`
Regular Expressions	Thompson NFA size (regex length m)	`O(m) states`
	Matching a text of length n	`O(n · m)`	Set-of-states simulation — no exponential blow-up.
	Backtracking engines (worst case)	`exponential`	Catastrophic backtracking on patterns like (a+)+b.
	Extra space	`O(m)`
Pushdown Automata (PDA)	Deterministic PDA run (input length n)	`O(n)`
	General CFG parsing (CYK)	`O(n³)`
	Extra space	`O(n) stack`
Turing Machine	Binary increment (n bits)	`O(n)`
	Palindrome check (n symbols)	`O(n²)`	The head runs back and forth n/2 times.
	Extra space	`The tape (unbounded)`
CYK Algorithm (Parsing Context-Free Grammars)	CYK parsing	`O(n³ · \|G\|)`	n² cells, up to n splits each, and \|G\| rules checked per split.
	Table size	`O(n²)`	One set of variables per substring.
	Extra space	`O(n²) table cells`
NFA to DFA Conversion (Subset Construction)	DFA states produced	`up to 2ⁿ`	Every subset of the n NFA states could be reachable.
	Work per DFA state	`O(n · \|Σ\|)`	Union the moves of each member for every symbol.
	Extra space	`Up to 2ⁿ table rows`

Computer Organization & Architecture

Topic	Case / operation	Time	Notes
Instruction Pipelining	Non-pipelined (n instructions, k stages)	`n · k cycles`
	Ideal pipeline	`k + (n − 1) cycles`	After the pipeline fills, one instruction finishes every cycle.
	Ideal speed-up	`≈ k (as n grows)`
Cache Memory Mapping	Direct mapped lookup	`1 tag comparison`
	k-way set associative lookup	`k comparisons (in parallel)`
	Fully associative lookup	`one comparison per line (in parallel)`	Fast but expensive hardware — used only for small caches like TLBs.
IEEE 754 Floating Point	Single precision (float)	`1 + 8 + 23 = 32 bits`	About 7 significant decimal digits.
IEEE 754 Floating Point	Double precision (double)	`1 + 11 + 52 = 64 bits`	About 15–16 significant decimal digits.
Booth's Multiplication Algorithm	n-bit multiplication	`n rounds`	Each round is at most one add/subtract plus one shift.
	Long runs of 1s in Q	`only 2 add/subtract operations per run`
	Extra space	`A, Q and Q₋₁ registers (2n + 1 bits)`
Restoring & Non-Restoring Division	Rounds (n-bit dividend)	`n`	One quotient bit per round.
	Restoring — add/subtract operations	`up to 2n`	A subtract every round, plus an add when restoring.
	Non-restoring — add/subtract operations	`n (+ 1)`	One per round, plus at most one final correction.
	Extra space	`Registers A (n + 1 bits), Q (n bits), M (n bits)`
Two's Complement	Negate a number	`O(n)`	Invert n bits and add 1, which may ripple a carry through all n bits.
	Add or subtract	`O(n)`	The same adder works for signed and unsigned numbers.
	Extra space	`n bits per number`
Ripple-Carry Adder	Add two n-bit numbers	`O(n)`	Each carry waits for the previous adder, so the delay is n full-adder delays.
	Carry-lookahead adder	`O(log n)`	Computes all carries in parallel using generate and propagate signals.
	Extra space	`n full adders (about 5 gates each)`

How to use this cheat sheet

Best, average and worst case can differ. Quick sort is O(n log n) on average but O(n²) in the worst case.
Amortised costs (like a dynamic array that sometimes doubles its size) are averaged over many operations, so a rare slow step doesn't change the overall bound.
Space matters too. Merge sort needs O(n) extra memory; heap sort sorts in place with O(1).
Not sure why a bound holds? Open the lesson and step through the 3D model — counting the steps yourself is the best proof.