Counting source lines tells you nothing about speed. One line can compare two integers. Another line can sort a million records.
Real analysis follows four steps. Name the input size. Name the operation you count. Write the total cost as a sum over the algorithm's structure. Then simplify.
Only the last step uses Big-O. The first three do the actual thinking.
Name the input size and the counted operation
Every analysis starts with two definitions. The input size, usually called n, measures how big the problem is. The counted operation is the unit of work whose growth matters.
"Sort 5,000 invoices by date" gives n = 5,000 and the operation "key comparison". "Find duplicates in a log file" gives n equal to the record count. The operation might be hashing a record or probing a table slot.
One algorithm can carry several costs at once. Merge sort performs O(n log n) comparisons and O(n log n) writes. Binary search performs O(log n) comparisons and O(1) writes.
Pick the resource you truly pay for. A database join counts disk reads. A graphics loop counts pixel writes. The same code has different bottlenecks in different systems.
Turn loop structure into a sum
Nested loops become nested sums. A full n by n grid traversal does one unit of work per cell:
work = sum over i of (sum over j of 1) = n x n = n-squaredAn inner loop that halves its range each pass costs log n per outer step. Run it n times and the total is n log n.
The last step is simplification. Keep only the dominant term and drop constants. The expression 3n² + 100n + 7 is O(n²). The n² term eventually dwarfs the rest.
Watch for one trap. The dominant term at large n may not dominate at your n. At n = 20, the 100n part equals 2,000 while 3n² equals 1,200. Asymptotics can mislead about small inputs you actually ship.
The same three functions below count halving steps in three languages. Run any of them to see the logarithmic curve directly:
// Count how many halving steps a binary search needs for n elements. // Each step discards half the range, so the count grows like log2(n). int binarySearchSteps(int n) { int steps = 0; // comparisons performed so far while (n > 0) { n = n / 2; // one comparison discards half the range steps++; // record that comparison } return steps; } // n = 1,000,000 returns 20; n = 1,000,000,000 returns 30.
Twenty comparisons cover a million elements. Ten more cover a billion. That slow growth is what O(log n) buys.
Recurrences describe splitting algorithms
Some algorithms define their cost in terms of themselves. Merge sort says "sort two halves, then merge them". A recurrence writes that sentence as math.
The common form is T(n) = aT(n/b) + f(n). It reads as follows: split into a pieces of size n/b, then spend f(n) combining them. The Master Theorem solves this form directly.
| Recurrence | Solution | Example |
|---|---|---|
T(n) = 2T(n/2) + n | O(n log n) | merge sort |
T(n) = 2T(n/2) + 1 | O(n) | tree traversal |
T(n) = 2T(n/2) + n² | O(n²) | heavy combine step per level |
The intuition compares two quantities. The work at the root is f(n). The work spread across one level is the rest. If the root dominates, the top level sets the cost. If the leaves dominate, the bottom level does.
You rarely need the full proof. You need the habit of writing the recurrence first. Once it is on paper, the theorem finishes the arithmetic.
Worst case, amortized, and expected answer different questions
Three guarantees sound similar. They fail in different ways. Keep them separate in every design document.
A worst case bound covers one operation on the nastiest input. Linear search is O(n) worst case because the target can sit last.
An amortized bound covers a sequence of operations. A dynamic array occasionally copies all n elements on resize. Across n appends the total is still O(n). Each append is therefore O(1) amortized, even though one append alone can cost O(n).
An expected bound needs a stated distribution over inputs. "Hash tables run in O(1)" means expected O(1) under uniform hashing. An adversary who picks colliding keys can push lookups to O(n).
Mixing these up causes real outages. A system passes review with an amortized claim and fails under load on one slow operation. A cache assumes average input and meets adversarial traffic instead.
Constants and memory hide behind the notation
Big-O erases constants, memory traffic, and cache behavior on purpose. That erasure is both its strength and its limit.
An O(n²) loop over 500 elements runs 250,000 iterations in microseconds. An O(n log n) algorithm that allocates across a terabyte of scattered nodes can run slower. The notation compares curves. It never measures your machine.
Use complexity to discard algorithms whose curves cannot fit your sizes. A quadratic scan of a billion rows is infeasible at any constant. Then measure the survivors on real data.
Also check which operation dominates. A sort that compares cheap integers differs from one that compares long strings. A structure with pointer chasing pays per hop what a contiguous scan pays per cache line. Count the expensive operation, not the convenient one.
Where analysis guides design and what to read next
Analysis decides capacity plans and algorithm picks. It tells a team whether a feature survives a tenfold traffic increase. It tells a reviewer whether a latency budget holds at peak load.
The method travels well beyond interviews. Database optimizers estimate join costs this way. Network stacks bound retransmission work this way. Game engines budget per-frame work this way.
Continue with what an algorithm is to connect invariants with cost. Then compare arrays and linked lists to see how memory layout changes the constants that Big-O hides.