Java Illuminated, 5th Edition

15.2 Running Time Analysis of Algorithms: Counting Statements

One simple method to analyze the running time of a code sequence or a method is simply to count the number of times each statement is executed and to calculate a total count of statement executions.

Example 15.1 is a method that calculates the total value of all the elements of an array of size n and returns the sum.

EXAMPLE 15.1 A Single Loop

public static int addElements( int [ ] arr )
{
  int sum = 0;                // ( 1 )
  int i = 0;                  // ( 2 )
  while ( i < arr.length )    // ( 3 )
  {
     sum += arr[i];           // ( 4 )
     i++;                     // ( 5 )
  }
  return sum;                 // ( 6 )
}

Let’s count how many times each statement is executed.

Assuming the array has n elements, we can develop the following analysis:

Statement

# Times ...