justificationto prove this claima crucial fact is that with each recursive call the number of candidate entries still to be searched 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 remaining candidates is either high low low high low <(mid low or high low low high <high (mid high initiallythe number of candidates is nafter the first call in binary searchit is at most / after the second callit is at most / and so on in generalafter the jth call in binary searchthe number of candidate entries remaining is at most / in the worst case (an 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 in other words (recalling that we omit logarithm' base when it is ) log thuswe have log which implies that binary search runs in (log ntime computing disk space usage our final recursive algorithm from section was that for computing the overall disk space usage in specified portion of file system to characterize the "problem sizefor our analysiswe let denote the number of file-system entries in the portion of the file system that is considered (for examplethe file system portrayed in figure has entries to characterize the cumulative time spent for an initial call to the disk usage functionwe must analyze the total number of recursive invocations that are madeas well as the number of operations that are executed within those invocations we begin by showing that there are precisely recursive invocations of the functionin particularone for each entry in the relevant portion of the file system intuitivelythis is because call to disk usage for particular entry of the file system is only made from within the for loop of code fragment when processing the entry for the unique directory that contains eand that entry will only be explored once