some simple algorithms and data structures if this were book about algorithmswe would now dive into careful analysis using something called recurrence relation but since it isn'twe will take much less formal approach that starts with the question "how do we know that the program terminates?recall that in we asked the same question about while loop we answered the question by providing decrementing function for the loop we do the same thing here in this contextthe decrementing function has the properties it maps the values to which the formal parameters are bound to nonnegative integer when its value is the recursion terminates for each recursive callthe value of the decrementing function is less than the value of the decrementing function on entry to the instance of the function making the call the decrementing function for bsearch is high-low the if statement in search ensures that the value of this decrementing function is at least the first time bsearch is called (decrementing function property when bsearch is enteredif high-low is exactly the function makes no recursive call--simply returning the value [low= (satisfying decrementing function property the function bsearch contains two recursive calls one call uses arguments that cover all of the elements to the left of midand the other call uses arguments that cover all of the elements to the right of mid in either casethe value of high-low is cut in half (satisfying decrementing function property we now understand why the recursion terminates the next question is how many times can the value of high-low be cut in half before high-low = recall that logy(xis the number of times that has to be multiplied by itself to reach converselyif is divided by logy(xtimesthe result is this implies that high-low can be cut in half at most log (high-lowtimes before it reaches finallywe can answer the questionwhat is the algorithmic complexity of binary searchsince when search calls bsearch the value of high-low is equal to len( )- the complexity of search is (log(len( )) finger exercisewhy does the code use mid+ rather than mid in the second recursive call recall that when looking at orders of growth the base of the logarithm is irrelevant