Tracing, as 0002.f described it, predicts what an algorithm will produce for one input. Analysis asks a broader question: how will the algorithm behave as its inputs grow, and how does it compare with other algorithms that do the same job? This section is built around that comparison. It begins with the measuring stick, Big-O notation. It then applies the measure to the two problems where competing algorithms are most familiar, sorting and searching. From there it widens to the trade-offs that analysis reveals, first between time and memory and then between exact answers and feasible ones. It ends with the general design techniques that recur across all of these algorithms, and with neural network training as an extended example of one of them making an enormous problem manageable.

Measuring growth#

Timing a program with a stopwatch tells you about one machine and one input. To compare algorithms in general, computer scientists describe how an algorithm's resource use, usually its number of steps and sometimes its memory, grows with the size of its input, called n. Big-O notation names that growth, and five classes cover most of the algorithms in this guide. From slowest to fastest growth, they are O(1), O(log n), O(n), O(n log n), and O(n²). An O(1), or constant, cost doesn't depend on n at all, as with reading a[5] or looking up a key in a map. An O(log n), or logarithmic, cost grows by about one step each time n doubles, which is what happens when each step halves the remaining data. An O(n), or linear, cost grows in proportion to n, as with one pass through an array. O(n log n), sometimes called linearithmic, is a little more than linear and is typical of the fastest general-purpose sorts. An O(n²), or quadratic, cost grows with the square of n and is typical of nested loops over the same data.

The practical meaning of these classes appears when the input grows. Doubling the input roughly doubles O(n) time and quadruples O(n²) time, so if a function takes about 1, 4, and 16 seconds on inputs of 100, 200, and 400, it is behaving quadratically. A function that compares every pair of values in an array, as when checking for duplicates with nested loops, makes about n(n-1)/2 comparisons, which grows as n², so a thousand-fold increase in data multiplies its time by about a million. A function that makes one pass and records each value in a map, checking whether it has appeared already, does a constant-time lookup per value and so is O(n), and the same thousand-fold increase multiplies its time by about a thousand.

Big-O describes growth at large sizes, and it deliberately ignores constant factors, so it doesn't settle every comparison. An algorithm that takes 1000n steps is O(n), and one that takes n² steps is O(n²), yet for every n below 1,000 the quadratic one does less work. Above 1,000, the linear one wins, and its advantage keeps growing. Growth classes describe which algorithm will win eventually, and for small inputs the constants can matter more. Analyses also distinguish best, average, and worst cases, since an algorithm can behave very differently on different inputs of the same size, as the sorts below show.

Sorting: one job, five algorithms#

Sorting is the classic setting for comparing algorithms, because many quite different methods produce the same result, and each has a different profile. Three properties distinguish them: time, as a growth class in the average and worst cases; space, especially whether the algorithm sorts in place, rearranging values within the original array instead of copying them into extra memory; and how it behaves on input that is already nearly sorted.

Selection sort repeatedly finds the smallest remaining value and swaps it into place. On the first pass it scans the whole array for the smallest value and swaps it into position 0, on the second pass it scans the rest for the next smallest and swaps it into position 1, and so on.

01 for (int i = 0; i < a.size[1] - 1; i = i + 1)
02   int m = i
03   for (int j = i + 1; j < a.size[1]; j = j + 1)
04     if (a[j] < a[m])
05       m = j
06   int t = a[i]
07   a[i] = a[m]
08   a[m] = t

Lines 02 to 05 find the position m of the smallest remaining value, and lines 06 to 08 swap it into position i, using a temporary variable. On [7, 4, 9, 2], the first pass swaps 2 into position 0, giving [2, 4, 9, 7], the second pass finds that 4 is already in place, and the third swaps 7 and 9, giving [2, 4, 7, 9]. Because the inner loop always scans every remaining value, selection sort makes n(n-1)/2 comparisons whatever the input's order, so 6 values take 15 comparisons even when they arrive already sorted. It is O(n²) and sorts in place. Its distinctive strength is that it makes at most n - 1 swaps, one per pass, and each swap moves a value a long distance straight to its final position. That matters when writing is much more costly than reading, as on flash memory, which wears with each write.

Bubble sort also makes repeated passes, but it compares and swaps adjacent values, carrying the largest remaining value to the end on each pass. One pass over [5, 1, 4, 2] swaps 5 with 1, then 5 with 4, then 5 with 2, giving [1, 4, 2, 5], so after the first pass the largest value is in its final position. Bubble sort is O(n²) on average, like selection sort, but it typically makes many more swaps, since values move one position at a time. A large value near the front can reach the end in a single pass, but a small value near the end moves only one position toward the front on each pass, so one such value can force about n passes, and input in reverse order is the worst case. A common improvement stops the sort after a pass that makes no swaps, which makes it fast on input that is already sorted, since one pass is enough to confirm the order.

Insertion sort builds a sorted section at the front of the array and inserts each new value into position within it, shifting larger values one place to the right. If the first three values of [3, 6, 8, 4, 1] are already sorted, the next step inserts 4 between 3 and 6, shifting 6 and 8 right, to give [3, 4, 6, 8, 1]. In code, an inner loop moves an index j backward past the larger values, and when it stops, j is one position before the gap, so the saved value goes into a[j + 1]. Insertion sort is O(n²) on average and sorts in place, but on nearly sorted data it is close to O(n), because each value moves only a short distance. This makes it a good choice for a list of records that is already almost in order, where selection sort would still make all n(n-1)/2 comparisons. It also suits data that arrives one value at a time, since keeping a sorted list sorted after each arrival requires moving only the new value.

The two remaining sorts are faster at scale, and both use recursion, the technique of 0002.f, to apply divide and conquer, described below. Merge sort recursively splits a list in half until each piece has one value, and then merges sorted halves back together by repeatedly taking the smaller front value of the two. Merging [1, 6] with [2, 4, 9] takes 1, then 2, then 4, then 6, then 9. Each level of splitting halves the lists, so there are about log₂ n levels, 10 for 1,024 values, and each level does about n work in merging, which gives O(n log n). That holds in all cases, which makes merge sort the choice when the worst case must be predictable. Its disadvantage is that merging needs additional memory to hold values as they are combined. Its way of working, merging sorted runs, also suits data too large to fit in memory, which can be sorted in chunks that are written to disk and then merged. A faster growth class doesn't make it always best, though: for a short array on a device with little memory, a simple in-place sort can be the better choice.

Quicksort chooses one value as a pivot and partitions the others around it, smaller values to one side and larger values to the other, and then recursively sorts each part. After partitioning, the pivot is in its final position, which is the number of values smaller than it, so with 6 as pivot in [9, 3, 7, 1, 6], two values are smaller and 6 ends at index 2. Quicksort averages O(n log n) and sorts in place, and in practice it is often the fastest of all, because of its low constant factors and good use of the processor's cache, which is why it often beats merge sort on large random arrays despite merge sort's better guarantee. Its weakness is an O(n²) worst case, which arises when partitions are unbalanced. If the first value is always the pivot and the list is already sorted, each partition leaves nearly everything on one side. Choosing the pivot at random, or as the median of three values, makes such unbalanced partitions much less likely.

Searching#

Searching shows how much the right algorithm can matter. Linear search checks each value in turn until it finds a match, which is O(n) and works on unsorted data. Binary search works only on sorted data. It compares the target with the middle value, and since the data is sorted, that one comparison shows which half could contain the target, so the other half is discarded. Halving repeatedly gives O(log n): about 20 comparisons for 1,000,000 values, where a linear search could need 1,000,000.

01 function find(int[] a, int target)
02   int low = 0
03   int high = a.size[1] - 1
04   int mid = 0
05   while (low <= high)
06     mid = (low + high) / 2
07     if (a[mid] == target)
08       return mid
09     elseif (a[mid] < target)
10       low = mid + 1
11     else
12       high = mid - 1
13   return -1

The bounds on lines 10 and 12 must exclude the middle value, which has already been checked. If line 10 said low = mid, then once low and high were next to each other or equal, mid could land on the same position again and again, the range would stop shrinking, and the loop would never end when the target is missing.

The two searches illustrate a cost that analysis makes visible. Checking 10,000 visitor IDs against 1,000,000 sorted member IDs takes up to about 10 billion comparisons by linear search and about 200,000 by binary search. But binary search needs sorted data, and sorting costs O(n log n). Sorting once pays off when a collection that changes rarely is searched many times, and it doesn't pay off for a single search: an unsorted list of 50 codes searched once a week is best searched linearly.

Trading space for time#

The map in the duplicate-checking example above is an instance of a general pattern. An algorithm can often run faster by using more memory, or use less memory by taking longer, and this is called a time and space trade-off. Caching stores results so they needn't be recalculated, as when a web application stores a profile page the first time it is built instead of spending 2 seconds rebuilding it on each visit. A map of values already seen avoids scanning an array again and again. The Fibonacci numbers give a vivid case: a recursive function that computes each value from the two before it recalculates the same values an exponentially growing number of times, while a version that stores each value as it is computed needs far fewer steps, at the cost of keeping the stored values. The same idea applies to a table built once and read many times, such as a list of running totals from which the sum of any range of days is one subtraction, or a table marking which numbers up to a limit are prime, so that each later check is a single lookup instead of a series of divisions. The trade doesn't always favor storage. If a precomputed table would be enormous and each result is quick to compute, storing it isn't worthwhile, and scarce memory on a small device may justify slower code. The choice depends on the size of the data and the limits of the system.

When exact answers are out of reach#

All the algorithms so far finish in reasonable time. Some problems, however, grow so quickly that no exact method can solve them at realistic sizes. A program that tries every seating arrangement of a class might work for 6 students, but the number of arrangements grows factorially, so with 25 students it will never finish. Finding the shortest route through 200 delivery stops has the same character, since the number of possible routes grows faster than exponentially. These are intractable problems at large sizes.

Programs facing such problems use heuristics, methods that find a good-enough result in reasonable time without guaranteeing the best one. Going next to the nearest unvisited stop is a heuristic for the delivery route. Pruning is another: a chess program stops exploring lines of play that are clearly worse than one it has already found, which shrinks the search without examining every possibility. Because a heuristic is judged by tests rather than proof, its good results on test cases suggest, but do not guarantee, similar results on future data. Whether a heuristic is acceptable is a judgment about needs. A schedule found in one second that costs 5% more than the best possible may be fine for a company that needs fast, near-best answers.

Design techniques#

Looking back over these algorithms, a few strategies recur, and naming them helps when designing new ones. Divide and conquer solves smaller versions of a problem and combines the results, as merge sort and quicksort do, and as an image-processing task does when it splits an image into quarters, processes each with the same procedure, and combines them. A greedy algorithm takes the choice that looks best at each step without reconsidering, as when a cash register makes change by repeatedly choosing the largest coin that fits the remaining amount, or when the nearest-stop heuristic picks the closest stop. Because a greedy algorithm never reconsiders, it can miss the best answer: it gives the fewest coins for coins of 25, 10, 5, and 1 cents, but with coins worth 4, 3, and 1 it pays 6 with three coins (4, 1, 1) where two 3s would do. Generate and test creates candidate solutions and checks each one, as when a password-testing tool tries combinations until one works, and the seating program above is generate and test on a scale that can't finish. Decomposition, from 0002.d, breaks a task into sub-problems that are solved separately, as when a chess project separates board display, move validation, and computer strategy into separately written parts.

An example: training a neural network#

Decomposition is also what makes modern machine learning feasible. A neural network can contain millions of adjustable weights, and training means finding settings for them that produce the desired outputs, a problem far too large to solve by trying settings. Training begins by comparing the network's actual outputs with the desired outputs, using a loss function that measures the difference between them. Backpropagation then works backward through the network's layers, using the chain rule from calculus to calculate how much each weight contributed to the error. If a network computes g(f(x)), with weights in both f and g, the chain rule divides the error at the output into a part due to g and a part due to f, finding the rate at which the loss changes with a weight in f by multiplying the rates along the chain from that weight to the loss. Each layer's calculation reuses values computed for the layers after it, so the huge problem is decomposed layer by layer into smaller calculations, and every weight can be adjusted in the direction that reduces the loss.

Analysis applies to the result as well as the process. If the loss keeps falling on the training data but starts rising on test data held back from training, the network is overfitting, fitting details of its training data that don't generalize to new data.¹

Algorithms like these become parts of larger programs, and the larger a program grows, the more it depends on how its parts are organized. The next section turns to object-oriented programming, which extends decomposition from algorithms to the structure of whole programs.

• Big-O notation: a description of how an algorithm's resource use grows with input size n
• in place: sorting within the original array, without significant extra memory
• selection sort: repeatedly swapping the smallest remaining value into place; n(n-1)/2 comparisons and at most n - 1 swaps
• bubble sort: repeatedly swapping adjacent values, carrying the largest remaining value to the end on each pass
• insertion sort: inserting each value into a growing sorted section; close to O(n) on nearly sorted data
• merge sort: recursively splitting a list and merging sorted halves; O(n log n) in all cases, with extra memory
• quicksort: partitioning around a pivot and recursively sorting each part; O(n log n) on average, O(n²) in the worst case
• pivot: the value around which quicksort partitions
• linear search: checking each value in turn; O(n)
• binary search: halving a sorted list with each comparison; O(log n)
• time and space trade-off: using more memory to save time, or more time to save memory
• intractable problem: a problem that grows too quickly to solve exactly at large sizes
• heuristic: a method that finds a good-enough result in reasonable time
• pruning: abandoning unpromising paths in a search
• divide and conquer: solving smaller versions of a problem and combining the results
• greedy algorithm: taking the best-looking choice at each step
• generate and test: creating candidate solutions and checking each
• decomposition: breaking a task into separately solved sub-problems
• loss function: a measure of the difference between a network's actual and desired outputs
• backpropagation: using the chain rule to work backward through layers, finding each weight's contribution to the error
• overfitting: fitting the training data in ways that don't generalize, shown by test loss rising as training loss falls

Practice: practice questions for 0002.k

1. MWC2, Classification: Neural: neural networks, backpropagation, and NumPy-style array indexing. ↩