then multiplied by the input valuewhich takes constant time thusthe cost of the factorial functionif we wish to measure cost in terms of the number of multiplication operationsis one more than the number of multiplications made by the recursive call on the smaller input because the base case does no multiplicationsits cost is zero thusthe running time for this function can be expressed as (nt( for ( we know from examples and that the closed-form solution for this recurrence relation is th(nthe final example of algorithm analysis for this section will compare two algorithms for performing search in an array earlierwe determined that the running time for sequential search on an array where the search value is equally likely to appear in any location is th(nin both the average and worst cases we would like to compare this running time to that required to perform binary search on an array whose values are stored in order from lowest to highest binary search begins by examining the value in the middle position of the arraycall this position mid and the corresponding value kmid if kmid kthen processing can stop immediately this is unlikely to be the casehowever fortunatelyknowing the middle value provides useful information that can help guide the search process in particularif kmid kthen you know that the value cannot appear in the array at any position greater than mid thusyou can eliminate future search in the upper half of the array converselyif kmid kthen you know that you can ignore all positions in the array less than mid either wayhalf of the positions are eliminated from further consideration binary search next looks at the middle position in that part of the array where value may exist the value at this position again allows us to eliminate half of the remaining positions from consideration this process repeats until either the desired value is foundor there are no positions remaining in the array that might contain the value figure illustrates the binary search method here is an implementation for binary search/return the position of an element in sorted array " /with value "kif "kis not in " "return length static int binary(int[aint kint - int length/ and are beyond array bounds while ( + ! /stop when and meet int ( + )/ /check middle of remaining subarray if ( [ ] /in left half if ( = [ ]return /found it if ( [ ] /in right half return length/search value not in