
1138 CHAPTER 15 Running Time Analysis
15.5 Running Time Analysis of Searching and Sorting Algorithms
In studying the running time of various searching and sorting algorithms,
we will look at the following scenarios:
■
best case
■
worst case
■
average case
Some methods have a very efficient running time. We mentioned earlier
that the running time of Binary Search was log n. Thus, searching a sorted
array of 1 billion items using Binary Search will only take 30 statement exe-
cutions since log (1 billion) is approximately 30.
Example 15.7 shows the code of the recursive binary search method intro-
duced in Chapter 13.
public static int recursiveBinarySearch