Empirical Complexity Analysis

The maximum contiguous subsequence sum (mcss) of an array is the largest sum you can acquire by adding up consecutive elements of an array. For example, consider the following array:

[5, -8, 7, 7, -1, 9, -6, -4, 5, -7]

The mcss of this array is 22, corresponding to the subsequence [7, 7, -1, 9]. Note that if the array consists of non-negative numbers then the subsequence is simply the entire array. We say that the mcss of an array consisting of all negative numbers is zero.

For this lab, you won’t be writing code to solve this problem. Instead, you’ll be analyzing the time complexity of various solutions to this problem.

• MaxContiguousSubsequenceSum.java

The three functions, compute1, compute2, and compute3, all return the mcss of the given array.

This file can also be found in the edu.grinnell.csc207.complexity package of this week’s repository. However, you should download this file to a folder and use javac and java to compile and execute this program independently of our Maven project for the week. The reason why are doing this is that we will measure the actual time it takes to execute the program in Part 1, and we don’t want to also measure the time Maven takes to run while doing so!

Part 1: Wall-clock Time

First, we will use the Unix time utility to test how long each function takes to run. For example, we can compile and run the program at a terminal window as follows:

> javac MaxContiguousSubsequenceSum.java
> time java MaxContiguousSubsequenceSum
Generating a random array of size 10... complete!
arr = [-3, 7, 6, -2, 1, -2, 3, -8, 3, 8]
compute1(arr) = 16
compute2(arr) = 16
compute3(arr) = 16

real    0m0.171s
user    0m0.089s
sys     0m0.045s

time runs the program (and arguments) passed to it and reports the time taken for that program to execute—the total time real, the amount of that time spent in user code user, and the time spent in system code sys.

On Windows, you can use Measure-Command to get a similar effect:

> javac MaxContiguousSubsequenceSum.java
> Measure-Command { java MaxContiguousSubsequence }

Note that when you use Measure-Command, the output of the program is suppressed in favor of reporting the time taken for it to run.

Now, modify the code and re-compile it so that the program runs only one of the functions, e.g., compute1. Run the program at least three times and record the average total time that you obtain for the function at a particular array size (the size is controlled by the size and range local variables in main.)

Repeat this process for each function and the following array sizes:

• 10
• 1000, and
• 100000.

Open up a spreadsheet program, e.g., Excel or OpenOffice, record your average time for each size, and graph the data you collect. The $x$-axis of your graph should be the size of the array and the $y$-axis should be the time taken.

Note that for some combinations of function and larger array sizes, the code might take too long to execute! In these cases, you can let the code run for a minute to see if it will complete. If it does not, you can record the time taken as “∞”.

Part 2: Counting Operations

While wall-clock is what ultimately matters when we talk about program performance, there are significant limitations to timing our programs over many inputs to assess its performs. One of those limitations is that wall-clock is highly sensitive to the particulars of the machine we run our programs on. We can avoid that limitation by instead counting the critical operations that a function performs. While the time a program takes to execute may vary widely on the state of computer, the program will perform the same number of critical operations no matter where the program executes. (This is true for the deterministic programs that we write in this course. With more complex programs, other factors become relevant which can make this method of analyzing program complexity less accurate!)

For mcss, we’ll consider the number of array accesses that each function performs. Let’s define an array access as any case where the function reads an array value (e.g., arr[0] + 1) or writes an array value (e.g., arr[0] = 10). Assuming that the array accesses dominates the runtime of the functions, then counting array accesses should be tantamount to measuring the time each function takes.

Augment the three functions so that rather than returning the mcss of the given array, they report the number of array accesses each function makes while computing the mcss. You can create a static int field called count in MaxContiguousSubsequence to easily record the counts. Use your augmented program to repeat the experiment from the first part of this lab: collect the number of array accesses required for each function for the following array sizes:

• 10
• 1000, and
• 100000.

For each function, graph the data you collected in your spreadsheet. The $x$-axis of your graph should be the size of the array and the $y$-axis should be the number of array accesses.

Compare the graphs from the previous parts of the lab and answer the following question in your project’s README.md file under the Write-up section.

How accurate is the operation counting method of measuring time complexity compared to the wall-clock method for understanding how the time complexity scales with the size of the input?

Finally, add your spreadsheet (downloading it from the Web if you used browser-based Excel) to your repository. You can place the spreadsheet in the root of your project directory, and add/commit like your other source files!