Java 6 Illuminated: An Active Learning Approach, 2nd Edition

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