ber of primitive operations are executed at each recursive call of method binary search hencethe running time is proportional to the number of recursive calls performed crucial fact is that with each recursive call the number of candidate entries still to be searched in the array list is given by the value high low moreoverthe number of remaining candidates is reduced by at least one half with each recursive call specificallyfrom the definition of midthe number of remain ing candidates is either or initiallythe number of candidate entries is nafter the first call to binarysearchit is at most / after the second callit is at most / and so on in generalafter the ith call to binarysearchthe number of candidate entries remaining is at most / in the worst case (unsuccessful search)the recursive calls stop when there are no more candidate entries hencethe maximum number of recursive calls performedis the smallest integer such that /