Recognize common growth patterns
Constant-time indexing, a linear scan, comparison sorting, and subset enumeration have different scaling behavior. Recognizing the structure helps choose an algorithm before writing it.
| Pattern | Typical growth | Why |
|---|---|---|
| One array access | O(1) | One fixed-index lookup |
| Visit every element | O(n) | One operation per element |
| Halve a search interval | O(log n) | Few reductions reach size one |
| Merge-sort levels | O(n log n) | Linear work at each logarithmic level |
| Enumerate all subsets | O(2ⁿ) | Each item is included or excluded |
For 20 elements, there are 1,048,576 subsets. For 30, there are 1,073,741,824. Faster hardware cannot turn unrestricted exponential enumeration into a scalable general solution.
A nested loop is not always quadratic: if the inner loop halves its bound, the analysis differs. Likewise, recursive syntax does not by itself imply exponential work.
Exercise
Classify scanning a matrix with r rows and c columns, sorting n records, and producing every pair of distinct records. Use both variables for the matrix rather than assuming it is square.
Check: an output containing all pairs already has quadratic size, so no algorithm can explicitly produce it in linear time.