Discrete Mathematics for Computer Science

570 CHAPTER 9 Recurrence Relations

Figure 9.4 represents the execution of BinSrch in looking for 9 in the set

{1, 2, 4, 6, 9, 13, 15, 18, 20, 21, 23, 25}

9

1 2 47 6 91 15 18 20 21 23 25

1 2 3 4 5 6 7 8 9 10 11 12

9

12 6

1 2 3 4 5

9

4 5

9

5

Figure 9.4 Using a binary search.

9.72 Complexity

For BinSrch, define T (n) to be the number of times that BinSrch will be executed when A

has n elements. The key operation in determining the complexity of the binary search is the

comparison of the element you are searching for with an element of the array. In the case

of BinSrch, one comparison between X and the middle element of A[Left]... A [Right] is

made to see if X is at that position. If X is not at that middle position, then the algorithm

is executed on the half of the elements of A that could still contain X. We can describe the

complexity of this procedure as

T(n) < T([n/2j) +^1 forfn >2

1 1 for n =1I

The function is an upper bound, because X can be found at some position causing the

search to terminate without making all the comparisons that would be necessary if X were

not in A. (The solution of this recurrence relation will follow as a corollary to the solution

of the recurrence relations that describe the complexity of the class of divide-and-conquer

algorithms presented later.)