An algorithm is a finite sequence of steps that solves a problem. It need not be complicated, deterministic, or executed by a computer: a step may say “choose a random number.” Data structures organize information; algorithms use that information to get a result. section 1.1
A simple procedure with substantial work
To choose an ad, estimate the revenue each candidate would generate for a user, then show the one with the highest expected revenue. The procedure is easy to state even if evaluating every candidate takes considerable computation. section 1.1
A useful algorithm solves a real problem, but its cost matters too. Complexity relates problem size to resources such as time or memory. Big O notation describes how that cost grows: reading the first array value is O(1), while summing n integers is O(n). A logarithmic cost grows much more slowly as input size increases. section 1.1
Figure 1.1 A graph comparing the growth curves for logarithmic, linear, quasilinear, quadratic, and exponential growth. The logarithmic curve is the shallowest, growing slowly, and the exponential curve is the fastest.
Compare growth curves before choosing between approaches: logarithmic growth stays shallow, while exponential growth rises fastest. section 1.1
The same algorithmic idea can cross domains. Backtracking search can find an item in a tree, color a map, or solve Sudoku; related search also appears in automatic code formatting. Conversely, a familiar problem can invite an unusual approach: immutable data structures can support undo and redo, and a basic Game of Life implementation offers a starting point for finding optimizations. section 1.0 section 4.1
