drawing an english ruler in analyzing the english ruler application from section we consider the fundamental question of how many total lines of output are generated by an initial call to draw interval( )where denotes the center length this is reasonable benchmark for the overall efficiency of the algorithm as each line of output is based upon call to the draw line utilityand each recursive call to draw interval with nonzero parameter makes exactly one direct call to draw line some intuition may be gained by examining the source code and the recursion trace we know that call to draw interval(cfor spawns two calls to draw interval( - and single call to draw line we will rely on this intuition to prove the following claim proposition for > call to draw interval(cresults in precisely lines of output justificationwe provide formal proof of this claim by induction (see section in factinduction is natural mathematical technique for proving the correctness and efficiency of recursive process in the case of the rulerwe note that an application of draw interval( generates no outputand that this serves as base case for our claim more generallythe number of lines printed by draw interval(cis one more than twice the number generated by call to draw interval( - )as one center line is printed between two such recursive calls by inductionwe have that the number of lines is thus ( - this proof is indicative of more mathematically rigorous toolknown as recurrence equation that can be used to analyze the running time of recursive algorithm that technique is discussed in section in the context of recursive sorting algorithms performing binary search considering the running time of the binary search algorithmas presented in section we observe that constant number of primitive operations are executed at each recursive call of method of binary search hencethe running time is proportional to the number of recursive calls performed we will show that at most log recursive calls are made during binary search of sequence having elementsleading to the following claim proposition the binary search algorithm runs in (log ntime for sorted sequence with elements