Divide and Conquer

Divide and conquer is a way of designing an algorithm: split a problem into smaller problems of the same kind, solve each by calling the algorithm on it, and combine the answers. Its cost is written as a recurrence, an equation that gives the running time on n items in terms of the running time on fewer, and that equation is how merge sort, quicksort and binary search are all costed. The topic opens on the three steps and where an algorithm's work sits among them, using the largest value of an array found by halves. It then reads the recurrence off three functions, solves one with a recursion tree that totals the work level by level, and shortcuts the method with the master theorem's three cases. A gotcha shows why four half-size calls are not as cheap as two, the code card prints the work on each level in three languages, and the exercise costs a way to multiply large numbers that wins by making one fewer call.