Java Illuminated, 5th Edition

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 take only 30 statement executions since log (1 billion) is approximately 30.

Example 15.7 shows the code for a recursive binary search.

EXAMPLE 15.7 Recursive Binary Search

public static int recursiveBinarySearch
                 ( int [ ] arr, int key, int start, int end )
{
  if ( start <= end )
  {
   // look at the middle element of the subarray
   int middle ...