A correct program can still be too slow to ship. It can also be fast on tests and slow on real data.
An algorithm is a finite procedure for solving a whole class of problems. A useful explanation of one answers two questions. Why does it produce the right result. What resources does it consume as the input grows.
This article shows how to hold both answers together. Correctness comes from an argument about the steps. Cost comes from counting what the steps do.
Every algorithm answers two questions
The first question is about trust. Does the procedure return the right answer for every valid input. A sorting routine that drops duplicates fails here. A search that misses absent keys fails here too.
The second question is about resources. How many comparisons does it perform. How many memory accesses. How does that count grow when the input doubles.
Beginners often answer only one of the two. They test correctness and ignore growth. Or they memorize a complexity label without knowing why it holds.
Strong engineers connect the two. The same structure that makes an algorithm correct usually determines its cost. Halving a range proves both that binary search finds the key and that it needs few steps.
Correctness rests on an invariant
An invariant is a claim that stays true at the same point in every loop iteration. It is the standard tool for proving that a loop works.
Consider binary search over a sorted array. The algorithm keeps two borders, lo and hi. The invariant says the target, if present, lies between them.
Each iteration reads the middle element. If the middle is too small, the left half cannot hold the target, so lo moves right. If the middle is too large, the right half cannot hold it, so hi moves left.
The range shrinks every step. A shrinking range over integers must become empty or hit the target. That is the whole proof. No step relies on luck or on the data looking typical.
Write the invariant before you write the loop. Most loop bugs are really missing invariants. The code looks plausible but maintains nothing.
Cost describes growth across inputs
Big-O notation gives an upper bound on growth, ignoring constant factors. It answers one question: what happens when n gets large.
Binary search needs about log₂(n) comparisons. Twenty comparisons cover a million items. Thirty cover a billion. Each doubling of the input adds exactly one comparison.
A linear scan needs up to n comparisons. A million items can cost a million checks. That gap is why sorted data plus binary search beats scanning once lookups repeat.
But Big-O hides everything except growth. It hides constants and data layout. It hides cache behavior and allocation. It hides the cost of one operation versus another.
A binary search performs fewer comparisons than a scan. Its memory accesses jump around the array instead of sweeping it. For a tiny array of 40 elements, the plain scan often wins because sequential data is easy for the processor to fetch.
Average-case claims need one more ingredient. They need a model of which inputs appear. Stating that model out loud is part of the analysis.
Amortized analysis answers a different question. It bounds a whole sequence of operations. A dynamic array occasionally copies every element, yet n appends still cost O(n) total. The rare expensive step spreads across many cheap ones.
Five techniques cover most problems
Most algorithms you meet reuse one of five shapes. Learn the shapes and you will recognize new problems faster.
Two pointers track two positions in ordered data. The example below checks whether any pair in a sorted array sums to a target. One pointer starts at each end. Each comparison moves one pointer inward, so the scan is linear.
#include <vector> // Decide whether any two numbers in a sorted array sum to target. // Each step moves one pointer, so the whole scan costs O(n). bool hasPairSum(const std::vector<int>& a, int target) { // Place one pointer at each end of the array. int lo = 0; int hi = (int)a.size() - 1; while (lo < hi) { int s = a[lo] + a[hi]; // sum of the current pair if (s == target) return true; // the pair fits exactly if (s < target) lo++; // sum too small: raise the left value else hi--; // sum too large: lower the right value } return false; // pointers met: no pair works }
A sliding window maintains a summary over a contiguous range that moves forward. It powers substring and subarray problems in linear time.
Divide and conquer splits a problem into smaller pieces and combines the answers. Merge sort splits the array, sorts each half, and merges. The recurrence for its cost is T(n) = 2T(n/2) + n.
Dynamic programming stores answers to overlapping subproblems instead of recomputing them. Naive Fibonacci recomputes the same values thousands of times. A table that remembers each value turns the cost linear.
Graph traversal makes relationships explicit as vertices and edges, then walks them. Breadth-first search fans out in rings. Depth-first search follows each path to its end.
For each technique, write down three things. The state it maintains. The condition that changes it. The work done per update. Then test empty input, duplicates, and adversarial ordering. Edge cases expose a missing invariant faster than any benchmark.
Access patterns decide speed on real hardware
Complexity gives a first map of cost. The machine fills in the rest. The data structure you pair with an algorithm controls which memory the hardware touches.
A binary search jumps across an array to the middle, then to a quarter. A linear scan walks addresses in order. The scan touches more elements but each access is predictable, so the prefetcher keeps up.
A linked traversal follows pointers from node to node. Each address depends on the previous load. The processor cannot fetch ahead, so every hop can cost around 100 nanoseconds.
A breadth-first search uses a queue and visits neighbors layer by layer. Its cost depends on how neighbor lists sit in memory. Compact arrays of neighbors run far faster than scattered node objects.
This is why measurement closes every analysis. Complexity chooses between curves that cross at your data size. A profile explains what one implementation truly pays.
Where cost reasoning pays off and what to read next
Cost reasoning shapes daily decisions. It tells you when an index is worth building. It tells you when a cache will help and when it will add overhead. It tells you which service slows down first as traffic doubles.
Practice the method on practical complexity analysis. Then compare representations in how representations shape operation cost.
MIT's Introduction to Algorithms course remains a strong companion for proofs and analysis.