Algorithmic Thinking and Complexity (Part 2): Design Patterns and Hardware

Book: The C++ Programmer’s Mindset
Author: Sam Morley
ISBN: 978-1-83588-842-1

The second half of Chapter 3 is a tour of algorithm design styles, then a hard turn toward what the hardware actually rewards. Morley’s message throughout: reuse known solutions first, then get clever only when you have to.

Previous: Algorithmic Thinking and Complexity (Part 1) | Next: Understanding the Machine (Part 1)

Design algorithms, do not reinvent them

Most problems are combinations of standard pieces. Chapters 1 and 2 were about recognizing those pieces. Here Morley says it plainly: do not reinvent the wheel.

Beating an existing algorithm’s complexity class is hard work. Strassen’s matrix multiply took years of math for a modest improvement over the naive O(n³) approach. The bigger wins often come from working with the hardware, not from a new asymptotic class on paper.

Iterative algorithms

The simplest pattern: walk inputs one after another in a loop. std::min_element and std::max_element are textbook examples.

Even if each step is O(1), scanning everything gives at least O(n) complexity. But iterative code is where you should start. It is easy to prove correct, easy to test, and easy to compare against fancier versions later.

The secret ingredient is the loop invariant: a condition that stays true every iteration. For max-finding, the invariant is “our candidate is ≥ every element seen so far.” Pick the right invariant and the algorithm almost writes itself. It also gives you the induction proof for free.

Recursive algorithms

Recursion has a base case (small enough to solve directly) and a recursive step (split the problem and call yourself on smaller pieces).

A naive recursive power function mirrors the iterative loop and stays O(n). A divide-and-conquer version computes x^n by squaring x^(n/2), hitting O(log n) multiplications. More bookkeeping (odd/even exponents, base cases), but the payoff is real.

In C++, recursion has costs: stack frames, no guaranteed tail-call optimization, risk of stack overflow on deep chains. constexpr recursion can bloat build times if you are careless. Divide-and-conquer often recurses only O(log n) times, so call overhead gets amortized across lots of work.

Divide and conquer

Split independent subproblems, solve them, combine results. Binary search (std::lower_bound, std::upper_bound) and quicksort are the classics.

Quicksort partitions around a pivot, recurses left and right, and needs no combine step when partitioning already places elements correctly. Complexity analysis often uses recurrence relations and the “master method” from Cormen. Morley does not state the full theorem but points you there.

Graphs, optimization, and dynamic programming

Graphs (vertices + edges) show up everywhere: paths, cycles, trees, weighted edges, Dijkstra for shortest paths. Search strategies matter: breadth-first vs depth-first. Many graph algorithms are greedy: pick the locally best edge or vertex by some score.

Optimization splits into linear (simplex method on a feasible region) and nonlinear (gradient descent, Nelder-Mead without derivatives). Gradient descent can get stuck in local minima. Branch and bound prunes search trees using heuristics.

Dynamic programming overlaps subproblems and memoizes results. It needs optimal substructure (the best overall solution uses best sub-solutions) and overlapping subproblems (reuse pays off). Shortest path fits; longest path in general graphs often does not.

Randomized algorithms help when worst-case inputs are rare (reverse-sorted data for sorting) or when injected randomness improves convergence (stochastic gradient descent).

Performance considerations on real hardware

The last section previews Chapter 4 in detail. Key points:

Use libraries

BLAS, optimized linear algebra, standard tools beat hand-rolled code almost every time. Pattern recognition before coding matters.

Cache-aware algorithms

CPUs wait on memory more than you think. Matrix multiply column-wise jumps through memory and trashes cache. Blocked algorithms (like BLAS uses) keep working sets small so data stays in cache. Same big-O, much better wall clock.

SIMD and vectorization

SIMD runs one instruction on many values. Compilers auto-vectorize simple index loops (std::span + integer indices) better than fancy range-zip iterators. Data must be contiguous. Aliasing (overlapping memory) blocks aggressive optimization. C has restrict; C++ does not, though separate vectors usually cannot alias.

Branch prediction

In tight numeric loops, unpredictable branches hurt. Speculative execution helps simple branches but created Spectre-class security issues. Morley flags the risk for security-sensitive code.

Chapter takeaway

You can have the right big-O and still lose on a real machine. Sometimes lowering complexity is not worth the research time. Rearranging memory access for cache and helping the compiler vectorize can win without changing the algorithm class at all.

Chapter 4 goes deep on the machine. This section is the bridge.

Previous: Algorithmic Thinking and Complexity (Part 1) | Next: Understanding the Machine (Part 1)