Notebook excerpts
A plain-text scan of every section in this note — the interactive, fully-styled version is in the reader above. Use whichever helps.
01
§ 01 Why complexity matters
Imagine you have two phonebooks. One has 10 names . The other has 10 million names . You're looking for "Sarah Khan".
02
§ 02 What Big O actually counts
Big O counts operations — the basic steps a computer takes to do its work. Comparisons, lookups, arithmetic, assignments. It expresses how that count grows as a function of the input size, usually called n .
03
§ 03 The shape, not the speed
Big O ignores constants and lower-order terms. If your algorithm does 3n² + 5n + 100 operations, the Big O is just O(n²) . We drop the 3, drop the +5n, drop the +100. Why?
04
§ 04 O(1) Constant time
The same amount of work, no matter how big the input is. One operation. The phonebook could have ten names or ten billion — looking up Sarah's number when the book is sorted by name lookup table takes the same blink.
05
§ 05 O(log n) Logarithmic
Every step halves the problem. Doubling the input size adds just one more step. This is the magic of "divide and conquer".
06
§ 06 O(n) Linear time
Look at every item once. Double the input → double the work. This is the natural-feeling complexity, the one humans intuit when they say "I'll check each one".
07
§ 07 O(n log n) Linearithmic
The "sorting sweet spot". Every good sort runs in this class: merge sort, heap sort, the typical quicksort. The intuition: you do log n rounds of work, each touching all n elements. n × log n total.
08
§ 08 O(n²) Quadratic
Look at every pair of items. A nested loop where both loops run n times. Doubling the input quadruples the work.
09
§ 09 O(n³) Cubic
Three nested loops. Look at every triple . Doubling n now means 8× the work. This is the regime where small problems take seconds and medium problems take hours.
10
§ 10 O(2ⁿ) Exponential
Every additional input doubles the work. The growth is terrifying . At n=30, you're at a billion operations. At n=60, you're at the age of the universe.
11
§ 11 O(n!) Factorial
The slowest practical complexity. n! = n × (n−1) × (n−2) × ... × 1. Beyond n=15 you've already hit a trillion operations. Beyond n=20 it's a quintillion. This is the brute-force "try every arrangement" complexity.
12
§ 12 The race
The fairest way to compare complexity classes is to give them all the same input size and count operations. Below, drag the slider to set n . Each bar shows how many operations that complexity class needs to finish.
13
§ 13 Growth curves
The race tells you who wins at one fixed n. The curves tell you the whole story. Here are all eight complexities plotted on the same axes — first on a regular scale, then on a log scale so you can actually see the slower ones.
14
§ 14 Where each one breaks
Every complexity class has a practical ceiling — the size of n above which the algorithm no longer finishes in reasonable time. The table below uses a rule of thumb: a modern CPU does about 10⁸ operations per second.
15
§ 15 Searching
Two algorithms, one task: find a target in an array of n items. The difference is whether the array is sorted.
16
§ 16 Sorting
The classic battleground for complexity. Every sorting algorithm sits in one of three speed classes — and which one matters enormously once n gets above a thousand.
17
§ 17 Data structures
Choosing the right data structure is half the battle. Here's how the basic operations cost across the common ones.
18
§ 18 Graph algorithms
For graphs, complexity is usually expressed in terms of both vertices (V) and edges (E). A graph with n nodes can have up to n² edges, so an algorithm that's O(V + E) is essentially linear in the graph's size, while O(V·E) starts to look quadratic on dense graphs.
19
§ 19 Identify the Big O
Read each snippet and pick the complexity. Click an option to check your answer — explanation appears below.
20
§ 20 Common mistakes
If you have for i in n: for j in n: ... , the complexity is O(n²), not O(n). Each iteration of the outer loop runs the entire inner loop. Always count the total number of operations, which means multiplying nested loop counts.
21
§ 21 Reference table
A single sheet to keep nearby. The first column is the complexity; the rest is everything you'd want to remember about it.