Counting

Take a minute to read the following function and make sure you understand how it works:

  public static int secondLargest(int[] numbers) {

    // Create an array to track the two largest keys
    int[] topTwo = new int[2];
    topTwo[0] = Integer.MIN_VALUE;
    topTwo[1] = Integer.MIN_VALUE;

    for (int i = 0; i < numbers.length; i++) {

      // If the current number is larger than the 2nd largest, 
      // the old 2nd largest should be replaced.
      if (numbers[i] > topTwo[0]) {
        topTwo[0] = numbers[i];
      }

      // Make sure the two largest are in the correct order
      if (topTwo[0] > topTwo[1]) {
        int tmp = topTwo[0];
        topTwo[0] = topTwo[1];
        topTwo[1] = tmp;
      }
    }
    return topTwo[0];
  }

Analyzing this algorithm involves selecting a basic operation and developing a function that describes how many time that basic operation occurs as a function of the input size. A standard basic operation for an algorithm like this is comparisons involving keys. In this case, such comparisons occur on lines 12 and 17 (highlighted).

One way to approach analyzing this code is to experimentally count the number of times the basic operation occurs by instrumenting the code with a counter variable that gets incremented for each operation:

  public static int secondLargest(int[] numbers) {
    int count = 0; // INSTRUMENT FOR EVALUATION

    // Create an array to track the two largest keys
    int[] topTwo = new int[2];
    topTwo[0] = Integer.MIN_VALUE;
    topTwo[1] = Integer.MIN_VALUE;

    for (int i = 0; i < numbers.length; i++) {

      // If the current number is larger than the 2nd largest,
      // the old 2nd largest should be replaced.
      count++; // COUNT COMPARISONS
      if (numbers[i] > topTwo[0]) {
        topTwo[0] = numbers[i];
      }

      // Make sure the two largest are in the correct order
      count++; // COUNT COMPARISONS
      if (topTwo[0] > topTwo[1]) {
        int tmp = topTwo[0];
        topTwo[0] = topTwo[1];
        topTwo[1] = tmp;
      }
    }

    System.out.printf("secondLargest actual steps:    T(%d) = %d\n\n", numbers.length, count);
    return topTwo[0];
  }

When this modified version of the function is executed, we'll see an exact count of how many times the basic operation occurred for the provided input size.

What do you expect to be printed when we execute this function as follows?

    int[] numbers = {3, 5, 1, 4, 2};
    int result = secondLargest(numbers);

Solution

secondLargest actual steps: T(5) = 10

The approach above would be described as empirical analysis because it involves running experiments to get a better understanding of the algorithm. Sometimes this approach is helpful because the behavior of an algorithm is too complicated to easily describe analytically. This is not one of those cases. In this case we can easily develop a formula that perfectly predicts the behavior of secondLargest.

Write the function below:

Solution

\(T(n) = 2n\)

Autograded Coding Exercises

Download the following three files:

Counter.java (Utility Class)
Counting.java (UNFINISHED)
CountingTest.java (Submission Tests)

Executing Counting.java should result in the following output:

maxTriple predicted steps: T(100) = -1
maxTriple actual steps:    T(100) = 294

countDouble predicted steps: T(16) = -1
countDouble actual steps:    T(16) = 80

tweakNumbers predicted steps: T(128) = -1
tweakNumbers actual steps:    T(128) = 135

doQuadraticWork predicted steps: T(100) = -1
doQuadraticWork actual steps:    T(100) = 1

doLogCubicWork predicted steps: T(100) = -1
doLogCubicWork actual steps:    T(100) = 1

doHalfQuadraticWork predicted steps: T(100) = -1
doHalfQuadtraticWork actual steps:    T(100) = 1

Your job for this activity is to complete the unfinished methods so that all of the actual and predicted values match, and correspond to the requirements described in the Javadoc statements.

Counting.java contains two types of unfinished methods that you will need to complete.

Prediction Methods

The file Counting.java contains several unfinished methods. Some require you to write Java expressions that correctly predict the number of steps required by the associated method. For example, we could write a function named predictSecondLargestSteps as follows:

  public static int predictSecondLargestSteps(int n) {
    return 2 * n;
  }

Jeopardy-Style Counter-Incrementing Methods

Other methods require you to create methods that perform some required number of steps. These methods won't do anything useful, they just provide practice in understanding the performance characteristics of nested and non-nested loops. For example:

  /**
   * This method must increment the counter exactly 10n times. The method must not include any
   * arithmetic calculations.
   */
  public static void doLinearWork(int n, Counter counter) {

    counter.increment(); // TODO - this should happen the correct number of times.

    System.out.printf("doLinearWork actual steps:    T(%d) = %d\n\n", n, counter.getCount());
  }

Take a minute to think about how you would accomplish this, then check the solution below.

Solution

  /**
   * This method must increment the counter exactly 10n times. The method must not include any
   * arithmetic calculations.
   */
  public static void doLinearWork(int n, Counter counter) {

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < 10; j++) {
        counter.increment(); 
      }
    }

    System.out.printf("doLinearWork actual steps:    T(%d) = %d\n\n", n, counter.getCount());
  }

Note that a solution like the following would give the same answer, but would violate the requirements of the problem.

  /**
   * This method must increment the counter exactly 10n times. The method must not include any
   * arithmetic calculations.
   */
  public static void doLinearWork(int n, Counter counter) {

    for (int i = 0; i < n * 10; i++) { // <-- THIS IS CHEATING!!!
      counter.increment(); 
    }

    System.out.printf("doLinearWork actual steps:    T(%d) = %d\n\n", n, counter.getCount());
  }