As with this example, recursive algorithms are often quite elegant. Analyzing the running time of a recursive algorithm takes a bit of additional work, however. In particular, to analyze such a running time, we use a recurrence equation, which defines mathematical statements that the running time of a recursive algorithm must satisfy. We introduce a function

that denotes the running time of the algorithm on an input of size

$,$ and we write equations that

must satisfy. For example, we can characterize the running time,

$,$ of the recursiveMax algorithm as

assuming that we count each comparison, array reference, recursive call,

calculation, or return as a single primitive operation. Ideally, we would like to characterize a recurrence equation like that above in closed form, where no references to the function

appear on the righthand side. For the recursiveMax algorithm, it isn't too hard to see that a closed form would be

$.$ In general, determining closed form solutions to recurrence equations can be much more challenging than this, and we study some specific examples of recurrence equations in another chapter, when we study some sorting and selection algorithms. We study methods for solving recurrence equations of a general form in Section $11\mathrm{.}2.$