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

Preparation

In a terminal window, navigate to the following directory:

  cd ~weinman/public_html/courses/CSC207/2010S/labs/code/analysis

There you will be able to access some pre-compiled class files that will allow you conduct experiments for the subsequent exercises. In all cases, the command

  java TestAnalysis exercise n

Will run the code fragment shown for the appropriate exercise number and report the value of the variable sum.

Exercises

Exercise 1

Loop1.java

public class Loop1 {

  public static int run(int n) {
    
    int sum = 0;

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

    return sum;
  }
}

What is the Big-Oh running time of Loop1?
Run the code with N = 10:
```
  java TestAnalysis 1 10
```
What value do you expect for N = 20?
Verify your prediction.
Try several more values of N.
Compare your analysis with the actual running times. Do they agree?

Exercise 2

Loop2.java

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;
  }
}

What is the Big-Oh running time of Loop2?
Run the code with several values of N.
```
  java TestAnalysis 2 n
```
Compare your analysis with the actual running times. Do they agree?

Exercise 3

Loop3.java

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;
  }
}

What value will result from N = 10? N = 20?
What is the Big-Oh running time of Loop3?
Run the code with a several values of N.
Compare your analysis with the actual running times. Do they agree?

Exercise 4

Loop4.java

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;
  }
}

What is the Big-Oh running time of Loop4?
Run the code with several values of N.
Compare your analysis with the actual running times. Do they agree?

Exercise 5

Loop5.java

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;
  }
}

What value will result from N = 4? N = 5?
Can you recall the closed-form for the value that will be returned? (If not, you might want to consult [Weiss, Section 5.2].)
What is the Big-Oh running time of Loop5?
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

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;
  }
}

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.
Test your predictions.
Based on your formula, or your observations from the code, what is the Big-Oh running time of Loop6?
Run the algorithm for a few more values of N and compare your analysis with the actual running times.

Exercise 7

Loop7.java

public class Loop7 {

  public static int run(int n) {

    int sum = 0;

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

    return sum;
  }
}

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

Exercise 8

Loop8.java

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;
  }
}

What is the Big-Oh running time of Loop8?
Run the code with several values of N.
Compare your analysis with the actual running times. Do they agree?
Given the results from b, what would you say the running time seems closer to?
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.

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.
Do any columns converge to zero?
Do any columns converge to a positive constant? If not, try adding larger N to overcome any low-order constants or large multiplying factors.
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.

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??
If the value in the upper-right corner is less than your query, where should you look next?
Can you repeat these tests based on your current location to devise a complete search algorithm?
What is the running time of your algorithm? (It should be better than the one in Exercise 10!)