CSC 207 Grinnell College Fall, 2014 Algorithms and Object-Oriented Design

# Algorithm Analysis

## Summary

In this lab, you will analyze the complexity of some code and experimentally test your analyses.

# Preparation

Load into Eclipse the java programs in the following directory:

`  cd ~walker/public_html/courses/207.sp12/labs/analysis`

TestAnalysis.java is the main program that calls the other pieces (Loop1.java ... Loop8.java). TestAnalysis.java allows you to conduct experiments for the subsequent exercises.

The program uses command-line input.

• The first command line argument is the exercise number.
• The second command line argument is a value for n.

To supply this information, select the "Run as Configurations..." option. Once the window comes up, be sure you have selcted TestAnalysis, and select the "Arguments" tab.

For example, to run the code for Exercise 1 with n=15, you would type

`  1 15`
in the arguments window, and then click "Run".

Note: In this lab, a variable NUMBER_REPETITIONS is specified to repeat a segment of code NUMBER_REPETITIONS2 times. This allows reasonable timings to be compared within the accuracy of the clock.

• If you find that experiments are going so fast that all times are close to 0, you may want to increase NUMBER_REPETITIONS (i.e., add a 0 to multiply by 10).
• If you find that experiments are taking a great deal of time, you might want to decrease NUMBER_REPETITIONS(i.e., remove a 0 to divide by 10).

# Exercises

## Exercise 1

Loop1.java
``````package analysis;

public class Loop1 {

public static int run(int n) {

int sum = 0;

for (int i=0 ; i < n ; i+=2)
sum++;

return sum;
}
}
``````
1. What is the Big-Oh running time of `Loop1`?
2. Run the code with N = 10:
3. Repeat this run several times, and observe what variation seems to occur within these timings.
4. What (range of) values do you expect for N = 20?
5. Verify your prediction.
6. Try several more values of N.
7. Compare your analysis with the actual running times. Do they agree?

## Exercise 2

Loop2.java
``````package analysis;

public class Loop2 {

public static int run(int n) {

int sum = 0;

for (int i=0 ; i < n ; i++)
for (int j=0 ; j < n ; j++)
sum++;

return sum;
}
}
``````
1. What is the Big-Oh running time of `Loop2`?
2. Run the code with several values of N.
3. Compare your analysis with the actual running times. Do they agree?

## Exercise 3

Loop3.java
``````package analysis;

public class Loop3 {

public static int run(int n) {

int sum = 0;

for (int i=0 ; i < n ; i++)
sum++;
for (int j=0 ; j < n ; j++)
sum++;

return sum;
}
}
``````
1. What value will result from N = 10? N = 20?
2. What is the Big-Oh running time of `Loop3`?
3. Run the code with a several values of N.
4. Compare your analysis with the actual running times. Do they agree?

## Exercise 4

Loop4.java
``````package analysis;

public class Loop4 {

public static int run(int n) {

int sum = 0;

for (int i=0 ; i < n ; i++)
for (int j=0 ; j < n * n ; j++)
sum++;

return sum;
}
}
``````
1. What is the Big-Oh running time of `Loop4`?
2. Run the code with several values of N.
3. Compare your analysis with the actual running times. Do they agree?

## Exercise 5

Loop5.java
``````package analysis;

public class Loop5 {

public static int run(int n) {

int sum = 0;

for (int i=0 ; i < n ; i++)
for (int j=0 ; j < i ; j++)
sum++;

return sum;
}
}
``````
1. What value will result from N = 4? N = 5?
2. Can you recall the closed-form for the value that will be returned? (If not, you might want to consult [Weiss, Section 5.2].)
3. What is the Big-Oh running time of `Loop5`?
4. If you wish, you may run the algorithm for several values of N and compare your analysis with the actual running times.

## Exercise 6

Loop6.java
``````package analysis;

public class Loop6 {

public static int run(int n) {

int sum = 0;

for (int i=0 ; i < n ; i++)
for (int j=0 ; j < n * n ; j++)
for (int k=0 ; k < j ; k++)
sum++;

return sum;
}
}
``````
1. A closed form analysis of `Loop6` is still possible, using the same formula as used in Exercise 5.b. Hazard a guess as to the formula and predict the result for N = 3 and N = 4.
2. Test your predictions.
3. Based on your formula, or your observations from the code, what is the Big-Oh running time of `Loop6`?
4. Run the algorithm for a few more values of N and compare your analysis with the actual running times.

## Exercise 7

Loop7.java
``````package analysis;

public class Loop7 {

public static int run(int n) {

int sum = 0;

for (int i=1 ; i < n ; i = i * 2 )
sum++;

return sum;
}
}
``````
1. What value will result from N = 4? N = 8? N = 16
2. What is the Big-Oh running time of `Loop7`?
3. Run the algorithm for a few values of N and compare your analysis with the actual running times.

## Exercise 8

Loop8.java
``````package analysis;

public class Loop8 {

public static int run(int n) {

int sum = 0;

for (int i=1 ; i <= n ; i++)
for (int j=1 ; j <= i * i ; j++)
if ( j % i == 0)
for (int k=0; k < j ; k++ )
sum++;

return sum;
}
}
``````
1. What is the Big-Oh running time of `Loop8`?
2. Run the code with several values of N.
3. Compare your analysis with the actual running times. Do they agree?
4. Given the results from b, what would you say the running time seems closer to?
5. What is it about the innermost loop that causes the actual results to differ widely from the Big-Oh?
Remember, Big-Oh is an upper bound!

## Exercise 9

Recall from [Weiss, Section 5.7] that another way to check whether some algorithm is O(F(N)) is to take the ratio of the empirical running time T(N) and F(N). Weiss says,
If F(N) is a tight answer for the running time, then the computed values converge to a positive constant. If F(N) is an overestimate, the values converge to zero.
In this exercise, you will perform an analysis similar to Figure 5.13 (p. 189) in the book for `Loop6`. An OpenOffice spreadsheet analysis.ods has been created for you that will simply your bookkeeping and analysis process.
1. Choose appropriate values of N for which to run `Loop6` and place these values (in increasing order) and the results of running the procedure for those N in the table.
2. Do any columns converge to zero?
3. Do any columns converge to a positive constant? If not, try adding larger N to overcome any low-order constants or large multiplying factors.
4. Does a column that converges to a constant agree with your analysis in Exercise 6?

# For those with extra time

Ok, now that you've thoroughly flexed your analysis muscles and given your CPU a very modest workout, let's switch gears (slightly).

Say we have an N×N matrix such that values are increasing from left to right in every row, and values are also increasing from top to bottom in every column. The following is an example:  1 2 4 6 3 5 7 9 4 8 11 13 7 9 12 14
One question we may ask is: How efficiently can we do search in such a matrix?

## Exercise 10

Suppose one algorithm implements a binary search on each row, and eventually indicates whether the value was found on any of the rows. What is the running time of this algorithm in terms of N?

## Exercise 11

Now someone crafty comes along an realizes they can do a more efficient search. Consider the value at the upper-right corner of the matrix.
1. If this value is greater than your query, where in the matrix should you look next? (I.e., where should you "move" to?) Left? Down? Something else??
2. If the value in the upper-right corner is less than your query, where should you look next?
3. Can you repeat these tests based on your current location to devise a complete search algorithm?
4. What is the running time of your algorithm? (It should be better than the one in Exercise 10!)

This document is available on the World Wide Web as

```http://www.walker.cs.grinnell.edu/courses/207.sp012/labs/lab-analysis.shtml
```

 Adapted from Mark Allen Weiss, Data Structures and Problem Solving Using Java, 3/e Exercises 5.15, 5.16, and 5.21 created 7 January 2009 by Jerod Weinman updated 23 February 2010 by Jerod Weinman revised 27-28 February 2012 by Henry M. Walker For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.