home
›
cheatsheets
›
computer_science
›
complexity_analysis
Free to read Every card and diagram, and Quiz me
2
Free account Star cards. Your Quiz me marks are kept, so next time you drill just what you missed
3
Pro All 52 answers on this sheet, My sheet across every topic, and PDFs
A free account keeps your stars and Quiz me marks. Pro adds all 52 answers on this sheet, My sheet across every topic, and PDFs.
/
Read
Quiz me
Comfortable
Compact
0
Click any code to copy it
Done 0 /0
To review 0
On this sheet
01 What Big-O means02 Counting steps in code03 Recursion & sorting04 Data structure costs05 Amortized cost06 Space & the call stack07 Constants, caches & disks08 Threads, cores & shards
The model Big-O says how work grows as the input grows. It drops constants and smaller terms, so 3n + 100 steps is O(n).Count how often the innermost step runs. Steps in a row add , nested loops multiply , and halving the input each time gives log n. Say which case you mean. Worst case is the usual promise. Average case assumes typical inputs, and amortized spreads rare costly steps over a whole sequence. Space is a separate budget. Count the extra memory, and remember that recursion holds one stack frame for every call that hasn't returned.Big-O hides constants. Small inputs, cache misses and disk reads can make the worse class win, so time it at your real n. COUNT turns code into a step count, and SIMPLIFY keeps only its growth class. RUN adds back the constants. CHECK times real inputs to test the class.
What Big-O means the notation, growth classes, and best vs worst case What Big-O tells you Say what Big-O measures How work grows as the input grows. It ignores machine speed, so it predicts how code scales.
Simplify a step count Drop constants and smaller terms. 3n + 100 is O(n), and n^2 + n is O(n^2).
Tell O, Theta and Omega apart O is an upper bound, Omega a lower bound, and Theta both. Unsorted search is O(n) and Omega(1).
Tip Most people say O and mean Theta, the tight bound. The difference matters only when the best and worst cases differ.
Growth rates, fastest first O(1) same O(log n) +1 step O(n) x2 O(n log n) just over x2 O(n^2) x4 time The top bars show all five classes taking the same time at size n. The lower bars show the time once n doubles.
Read one array slot by its index O(1) Constant.
Binary search sorted data O(log n) Logarithmic.
Scan every item once O(n) Linear.
Sort n items by comparing them O(n log n) Linearithmic.
Compare every pair O(n^2) Quadratic.
Try every subset O(2^n) Exponential.
Try every ordering O(n!) Factorial.
Tip At a million items, O(log n) is about 20 steps and O(n^2) is a trillion.
Best, average and worst case Quote the worst case The slowest any input of size n can make it. Plan around this one.
Quote the average case The expected cost over typical inputs. Use it when rare slow inputs are acceptable.
Quote the best case The luckiest input. Unsorted search is O(1) when the target sits first. It guarantees nothing.
Quote a randomized algorithm's expected time An average over its own coin flips, so it holds for every input.
Trap Randomized quicksort is still O(n^2) in the worst case. What changes is that no input can force it.
P, NP and NP-complete Tell P from NP You can solve a P problem in polynomial time. You can check an NP answer in polynomial time.
Define NP-complete and NP-hard An NP-complete problem is in NP, and every NP problem reduces to it. NP-hard needs only the reduction.
Handle an NP-hard problem at work Stop looking for a fast exact algorithm. Approximate, use a heuristic, or search every option while n is small.
Tip Travelling salesman and knapsack optimization are NP-hard. Whether P equals NP is still an open question.
Counting steps in code turn loops and calls into a Big-O Loops in a row or nested Cost one loop over n items O(n) Count how often the body runs. Ten small steps inside still make it O(n).
Cost two loops, one after the other O(n) Add them. O(n) + O(n) is still O(n).
Cost a loop inside a loop O(n^2) Multiply them. The body runs n * n times.
Cost an inner loop that runs up to the outer counter O(n^2) The counts 1 + 2 + ... + n add up to about n^2 / 2.
Cost an inner loop with a small fixed bound O(n) A fixed bound is a constant, so only the outer loop counts.
Cost a loop that stops at the square root of n O(sqrt n) The loop's bound sets the class, not the work inside it.
Trap A call inside a loop multiplies too. An O(n) call inside an O(n) loop makes it O(n^2).
Halving gives log n Halve the range at every step O(log n) 1,000 items take about 10 steps, and a million about 20.
Double the input to an O(log n) algorithm It takes one more step, not twice the work.
Explain why the log's base doesn't matter Changing base multiplies by a constant. log2 n and log10 n are both O(log n).
Tip The base still sets real costs. A B-tree with a fanout of 100 is far shorter than a binary tree, so it reads the disk fewer times.
Two inputs, two variables Loop over two collections, one after the other O(n + m) Merging two sorted arrays costs this too.
Nest a loop over one collection inside the other O(n * m) Not O(n^2). The two sizes can differ wildly.
Trap Don't use one n for two inputs. It hides which input dominates the cost.
Hidden costs inside one line Build a string with += in a loop O(n^2) In most languages strings are immutable, so each += copies everything so far.
Build the same string in linear time "".join(parts) Or use a StringBuilder. Either one copies once, so it's O(n).
Call indexOf on an array inside a loop O(n^2) indexOf scans the array. A Set lookup brings it back to O(n) on average.
Tip V8, the engine in Chrome and Node.js, skips the += copy once a string reaches 13 characters.
Trap A set rebuilt on every pass hides a loop too. Build it once, before the loop.
Recursion & sorting recurrences, call trees, memoization and sort costs Cost a recursive function n n/2 n/2 n/4 n/4 n/4 n/4 = n = n = n merge sort Each row of calls adds up to n work. Halving gives log n rows, so n log n in total.Write the recurrence Count the calls, their input size, and the work outside them. Merge sort is T(n) = 2T(n/2) + O(n).
Recurse once on half the input O(log n) Like binary search, T(n) = T(n/2) + O(1).
Recurse twice on halves, plus linear work O(n log n) Merge sort.
Recurse twice, on n-1 and n-2 O(2^n) Naive Fibonacci. The call tree doubles at every level.
Trap Count the branching factor. One call on half the input makes about log n calls, but two calls make n leaves.
Master theorem Solve T(n) = aT(n/b) + f(n) Compare f(n) with n^(log_b a). The bigger one sets the answer.
Solve the recurrence when both terms tie Multiply the shared term by log n. Merge sort ties at n, so it's O(n log n).
Trap It only fits equal-sized subproblems that shrink by division. For uneven splits, T(n-1), or an f(n) between the cases, expand by hand.
Exponential blowup and memoization Memoize recursive Fibonacci O(n) It computes each value once. The cache and the stack each hold O(n).
Compute Fibonacci with a bottom-up loop O(n) Keep only the last two values for O(1) space.
Spot accidental exponential blowup Two or more calls per level, depth that grows with n, and arguments that repeat.
Trap Backtracking and unmemoized dynamic programming hide the same blowup. Cache the repeated states.
Sorting costs Sort with merge sort O(n log n) On every input, with O(n) extra space.
Sort with quicksort O(n log n) On average. A fixed pivot on sorted input gives O(n^2).
Sort with heap sort O(n log n) In place, with O(1) extra space.
Sort with insertion sort O(n^2) Near O(n) on nearly sorted data, and the fastest on tiny arrays.
Sort small integer keys with counting or radix sort O(n) No comparisons, so the n log n floor doesn't apply.
Tip No comparison sort beats O(n log n). It must tell apart all n! orderings of the input.
Data structure costs what each operation costs, and why Arrays Read or write slot i O(1) The address is simple arithmetic, so there's no scan.
Search an unsorted array O(n) A sorted one takes O(log n) with binary search.
Append at the end O(1) While spare capacity remains. A full array must grow first.
Insert or delete at the front or middle O(n) Every later element shifts one slot.
Linked list vs array Get the i-th item of a linked list O(n) You walk from the head. An array does it in O(1).
Insert or delete at a node you hold O(1) Relink two pointers. An array shifts items instead, which is O(n).
Append to a linked list O(1) Only with a tail pointer.
Trap The O(1) insert assumes you already hold the node. Finding it first costs O(n).
Hash tables Look up, insert or delete a key O(1) On average. The hash points straight at a bucket.
Look up a key when many keys share a bucket O(n) A weak hash or a nearly full table causes it.
Walk the keys in sorted order A hash table has no order. Sort the keys first for O(n log n), or use a balanced tree.
Stop crafted keys forcing lookups to O(n) Mix a secret random seed into the hash. SipHash is built for this.
Tip Java's HashMap doubles its buckets once it passes 75% full. Resizing is costly, but it keeps buckets short.
Binary search trees Search, insert or delete in a balanced tree O(log n) Red-black and AVL trees rotate to keep the height near log n.
Search a tree built from sorted keys O(n) Each key becomes the right child of the last, so the tree is a chain.
Find the next key up, or where a range starts O(log n) In a balanced tree. A hash table can't answer this.
Binary heaps Peek at the min O(1) It's always the root.
Insert an item O(log n) It bubbles up from the bottom, at most one swap per level.
Build a heap from n items O(n) Bottom-up heapify. Most nodes sit near the leaves.
Search for any value O(n)
Tip A binary heap is a complete tree, so its height is always log n.
Trap Building a heap with n inserts is O(n log n). Bottom-up heapify does it in O(n).
Graph traversal Run BFS or DFS on an adjacency list O(V + E) It visits each vertex once and each edge once, or twice if undirected.
Run BFS or DFS on an adjacency matrix O(V^2) Each vertex reads a full row of V entries.
Pick a matrix over a list Only for dense graphs, where E nears V^2. Then both cost about the same.
Amortized cost cheap on average, with rare costly steps Append to a dynamic array 1 2 4 8 16 Each cell is an append. A number marks an append that finds the array full and copies that many items.
Append with spare capacity O(1)
Append to a full array O(n) Allocate a bigger block and copy every item.
Spread the cost over n appends O(1) That's the amortized cost. With doubling, the copies add up to about 2n.
Grow by a fixed chunk instead O(n) That's per append, amortized. Only growth by a factor keeps it O(1).
Tip Java's ArrayList grows by 1.5x, not 2x. Any constant factor keeps append O(1) amortized.
Amortized vs average case Define amortized cost The worst-case total of a sequence, divided by its length. There's no probability in it.
Define average-case cost The cost averaged over an assumed spread of inputs. A hostile input can break it.
Prove an amortized bound Show that any n operations cost O(n) in total. Use the aggregate, accounting or potential method.
Tip Dynamic array append is amortized O(1). Hash lookup is average O(1), so crafted keys can still force O(n).
When the rare spike matters Explain why amortized O(1) can miss a deadline One resize is O(n). A p99 target fails on that one call, whatever the average.
Resize a hash table without a pause Keep both tables live and move a few buckets on each operation. Redis does this.
Preallocate when you know the size new ArrayList<>(n) No resize copies and no spikes. Overshoot wastes memory.
Trap Garbage collection pauses hit the tail the same way. Bound the worst case, not the average.
Space & the call stack the extra memory an algorithm holds Time vs space Sum an array O(n) time, but O(1) space. It keeps one running total.
Find two numbers that add up to a target Nested loops take O(n^2) time. A hash set takes O(n) time on average and O(n) space.
Process a stream in constant space Keep a fixed set of values, like a sum and a count. Anything that grows breaks the claim.
Get an exact median from a stream Not in constant space. Accept an approximation or a bounded window.
Trap Extra memory helps only while it fits. A table too big for the cache or RAM turns lookups into misses or page faults.
Recursion depth and the stack Cost the space of recursion depth d O(d) One stack frame per open call. Halving keeps depth at log n.
Recurse once per item over a long list O(n) A million calls deep overflows a stack of 1 to 8 MB.
Switch to a loop with an explicit stack Same O(depth) space, moved to the heap. The heap holds gigabytes, not megabytes.
Turn tail recursion into a loop O(1) An accumulator replaces the stack.
Trap Python and V8 skip tail-call optimization, so deep recursion still overflows there.
Probabilistic structures Test membership in a few bits per item Use a Bloom filter. It never misses a member, but gives rare false positives.
Count billions of distinct items in kilobytes Use HyperLogLog. An exact set would need gigabytes.
Count how often items appear, in fixed memory Use a count-min sketch. It can over-count but never under-counts.
Trap Skip them where a false positive is costly, like a security check. Confirm hits against the real data.
Constants, caches & disks what Big-O hides on real hardware When the worse Big-O wins Sort a tiny array Insertion sort beats merge sort below about 10 to 50 items. Sort libraries switch to it.
Decide whether a better exponent pays off Benchmark at your n. Some algorithms only win on inputs no machine can hold.
Multiply matrices in practice Plain O(n^3) or Strassen's O(n^2.807). The O(n^2.37) methods carry huge constants.
Caches and memory layout Compare an L1 cache hit with a RAM access About 1 ns against about 100 ns.
Compare an array scan with a linked-list walk Both O(n). The array wins, because it loads 64-byte cache lines and the CPU reads ahead.
Pick between a contiguous sort and a pointer-chasing pass The O(n log n) sort can beat the O(n) pass. Cache misses, not comparisons, set the pace.
Tip Profile with cache-miss counters before you trust the asymptotic winner.
Data bigger than RAM Cost a random read from disk About 1,500 times a RAM read on an SSD, and 100,000 times on a spinning disk. Count block transfers, not steps.
Index data on disk O(log_B n) That many block reads with a B-tree. It packs B keys into each node.
Sort data bigger than RAM External merge sort. It streams large sorted runs.
Scale from a million to a billion items O(n^2) takes decades, so only near-linear algorithms stay practical. Budget IO too.
Measure the constants Read a doubling test Time doubles for O(n), quadruples for O(n^2), and adds a step for O(log n).
Check an O(n) claim Time per item stays flat. If it climbs, the analysis missed a cost.
Confirm the exponent Plot time against n on log-log axes. A straight line's slope is the exponent.
Get numbers you can trust Warm up the JIT, use realistic data, and average many runs.
Threads, cores & shards what concurrency adds to the cost Locks and parallel speedup Wrap a hash map in a lock Lookups stay O(1) on average, but threads wait in line. Contention sets the real cost.
Cost an atomic write under contention Hundreds of cycles, as the cache line moves between cores.
Sum an array on many cores Still O(n) work, but the span drops to O(log n).
Find the speedup limit with Amdahl's law 10% serial work limits you to 10x, even on 1,000 cores.
Trap Small or dependent tasks can run slower in parallel. Starting threads and syncing them costs more than it saves.
Sharded systems Query one shard O(log n) Just the local index cost.
Fan a query out to every shard The local cost times the shard count, and you wait for the slowest reply.
Find what dominates the cost Bytes moved over the network, more than any step in memory.
Trap A hot key piles load on one node. An O(1) design then behaves like O(n) there.
Nothing matches. Try a shorter word, or clear the search.
Practice Guided practice One question at a time, with the ones you miss coming back. Practice 57 interview questions Full answers, from beginner to expert.
Found this useful? Pass it on.
Share on LinkedIn
Share on X
Copy link
This sheet stays free. With Pro , you can:
Every answer on this sheet. Read the full answer to all 52 questions it links, not just the 7 free ones.My sheet. The cards you star and the ones you miss in Quiz me, from every sheet, on one page to quiz and print.PDFs. Download this sheet and My sheet, laid out for A4, with every question a link to its answer.The rest of Pro. Every answer in the question library, and 1,000 AI credits a month.
