In Section 4.2 we prove by induction that the number of lines printed by a call to draw interval(c) is 2c 1. Another interesting question is how many dashes are printed during that process. Prove by induction that the number of dashes printed by draw interval(c) is 2c+1 c 2.

4.2. Analyzing Recursive Algorithms 163 Justification: To prove this claim, a crucial fact is that with each recursive call the number of candidate entries still to be searched is given by the value high - low+1 Moreover, the number of remaining candidates is reduced by at least one half with each recursive call. Specifically, from the definition of mid, the number of remain- ing candidates is either low +high high - low+1 (mid-1)-low 1 = low or low +highhigh- low1 high-(mid + 1) + 1 = high Initially, the number of candidates is n; after the first call in a binary search, it is at most n/2; after the second call, it is at most n/4; and so on. In general, after the jth call in a binary search, the number of candidate entries remaining is at most n/2 In the worst case (an unsuccessful search), the recursive calls stop when there are no more candidate entries. Hence, the maximum number of recursive calls performed is the smallest integer r such that 2 In other words (recalling that we omit a logarithm's base when it is 2), r > logn. Thus, We have r-|logn +1, which implies that binary search runs in O (log n) time. 4.2. Analyzing Recursive Algorithms 163 Justification: To prove this claim, a crucial fact is that with each recursive call the number of candidate entries still to be searched is given by the value high - low+1 Moreover, the number of remaining candidates is reduced by at least one half with each recursive call. Specifically, from the definition of mid, the number of remain- ing candidates is either low +high high - low+1 (mid-1)-low 1 = low or low +highhigh- low1 high-(mid + 1) + 1 = high Initially, the number of candidates is n; after the first call in a binary search, it is at most n/2; after the second call, it is at most n/4; and so on. In general, after the jth call in a binary search, the number of candidate entries remaining is at most n/2 In the worst case (an unsuccessful search), the recursive calls stop when there are no more candidate entries. Hence, the maximum number of recursive calls performed is the smallest integer r such that 2 In other words (recalling that we omit a logarithm's base when it is 2), r > logn. Thus, We have r-|logn +1, which implies that binary search runs in O (log n) time