Algorithmic Complexity and Dynamic Programming
A vocabulary for judging how any algorithm scales, and three techniques for making slow ones fast
Big Idea: An algorithm's cost is not a single number of seconds - it is a function of the input size. Big-O notation captures how that cost grows as the input grows, ignoring machine speed and constant factors so you can compare two algorithms on paper before writing a line of code. Once you can name a cost, you can attack it: divide and conquer, memoization, and dynamic programming turn many exponential algorithms into polynomial ones.
By the end you will be able to:
- read and write Big-O bounds and justify why constants and lower-order terms drop,
- rank the common complexity classes and reason about time/space trade-offs,
- recognise the divide-and-conquer pattern behind algorithms such as merge sort,
- convert an exponential recursion into a linear one with memoization, then into a bottom-up dynamic program.
1. Why we count operations, not seconds
Timing an algorithm with a clock measures your CPU, your compiler flags and today's cache state as much as the algorithm itself. To reason about the algorithm alone we count the number of basic operations it performs as a function of the input size n, and we ask how that count behaves when n becomes large.
Suppose a routine performs 3n + 5 comparisons. The +5 is a fixed start-up cost and the 3 is a per-element constant that depends on the machine. For large n the term that decides the outcome is n. We therefore say the routine is O(n): its running time grows linearly, and doubling the input roughly doubles the work.
Analogy. When deciding whether to walk or drive across a country, the top speed of the car matters less than the distance. Over a long enough trip the shape of the growth - not the constant factor - dominates. Big-O reports the shape.