5.2. Analyzing Recursive Algorithms 203 Drawing an English Ruler In analyzing the English ruler application from Section 5.1.2, we consider the fun- damental question of how many total lines of output are generated by an initial call to drawlnterval(c), where c denotes the center length. This is a reasonable bench- mark for the overall efficiency of the algorithm as each line of output is based upon a call to the drawLine utility, and each recursive call to drawlnterval with nonzero parameter makes exactly one direct call to drawLine. Some intuition may be gained by examining the source code and the recur- sion trace. We know that a call to drawlnterval (c) for c 0 spawns two calls to drawlnterval(c 1) and a single call to drawLine. We will rely on this intuition to prove the following claim Proposition 5.1: For c 20, a call to drawlnterval (c reslts in precisely 2 lines of output. -1 Justification: We provide a formal proof of this claim by induction (see Sec- tion 4.4.3). In fact, induction is a natural mathematical technique for proving the correctness and efficiency of a recursive process. In the case of the ruler, we note that an application of drawlnterval(0) generates no output, and that 20--1-1- 0. This serves as a base case for our claim More generally, the number of lines printed by drawlnterval(c) is one more than twice the number generated by a call to drawlnterval(c1), as one center line is printed between two such recursive calls. By induction, we have that the number of lines is thus l + 2 . (2c-i-1 )-1 + 2c-2-2c-1 This proof is indicative of a more mathematically rigorous tool, known as a recurrence equation, that can be used to analyze the running time of a recursive algorithm. That technique is discussed in Section 12.1.4, in the context of recursive sorting algorithms