DataslopeAlgorithms Intuition
Thinking about cost — Big-O at the gut level, plus the standard algorithms you'll use every day.
You can write a program that produces the right answer and is still unusable because it takes hours when it should take milliseconds. Performance is a separate axis from correctness. Learning to feel how expensive an algorithm is — without doing formal proofs — is one of the most valuable software-engineering skills.
A working mental model of cost
For most everyday code, you care about a simple question: how many operations do I do as the input grows? That count is the algorithm's time complexity.
| Notation | Pronounced | Rough feel |
|---|---|---|
| O(1) | "constant" | Same time no matter the input size. |
| O(log n) | "log n" | Doubling n adds one step. |
| O(n) | "linear" | Doubling n doubles the work. |
| O(n log n) | "n log n" | Slightly worse than linear; the sweet spot for sorting. |
| O(n²) | "n squared" | Doubling n quadruples the work. Fine for n=1000, painful for n=100,000. |
| O(2ⁿ) | "exponential" | Adding one input element doubles the time. Only tractable for tiny n. |
You don't need to be a theorist. Just learn to recognize the shape: nested loops over the same data are usually quadratic; a single pass is linear; halving the search space each step is logarithmic.
Counting in code
For n=8 the difference is invisible. For n=10,000,000 the linear loop takes a moment; the quadratic loop is hopeless.
The standard algorithms
Most of the algorithms you'd want are already in <algorithm>.
They're tested, fast, and read clearly. Reach for them before
writing a loop.
A few rules of thumb:
std::sortis O(n log n) — your default sorting tool.std::find,std::count,std::accumulateare linear.std::lower_bound,std::upper_bound,std::binary_searchrequire a sorted range and are logarithmic.- Algorithms that produce output (
std::copy,std::transform) generally match the size of the input.
Algorithmic thinking, step by step
Suppose you must check whether any two of n numbers sum to a
target. Three approaches with very different costs:
| Approach | Cost | Idea |
|---|---|---|
| Try every pair | O(n²) | Nested loops |
| Sort, then two pointers | O(n log n) | Sort once; walk from both ends |
| Hash set | O(n) average | For each x, check if target - x is in a set |
The fastest is also the easiest to get wrong (hash collisions, edge cases). The point of these chapters is not to memorize "the best" algorithm — it's to recognize that multiple approaches exist and that the cost is a deliberate choice.
Premature optimization vs. algorithmic thinking
The famous quote "premature optimization is the root of all evil" is about micro-optimizations — tweaking individual instructions, caches, branch predictors. It does not mean "ignore complexity." Picking O(n²) when O(n log n) is one extra line of code is not optimization, it's negligence at scale.
The right discipline:
- Pick the right algorithmic shape from the start.
- Write the clearest possible code at that complexity.
- Measure. Only then optimize the hot spot.
Challenge
Given a hard-coded vector of 7 integers, sort it ascending and print the median (middle element). Use std::sort. Expected output for {8, 1, 6, 4, 2, 9, 3} is 4.
Test your understanding
Two nested loops, each iterating from 0 to n, that do constant work per pair — what is the time complexity?
O(n)
O(log n)
O(n²)
O(n log n)
Why does std::lower_bound require a sorted range?
The compiler enforces it.
It does not; it works on any range.
It uses binary search internally; binary search is correct only if the elements are arranged in order.
It uses hashing.
Next: the containers that hold those algorithms' inputs — and their trade-offs.