Algorithm Analysis

Summary

Preparation

Load into Eclipse the java programs in the following directory:

  cd ~walker/public_html/courses/207.fa18/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

Note: In this lab, a variable NUMBER_REPETITIONS is specified to repeat a segment of code NUMBER_REPETITIONS² 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

General Notes:

1. In each of the folloiwng exercises, when you are asked to determine the Big-h running time, you will need to start with a micro-analysis. In your analysis, use the following constants for the time it takes a machine to do specific operations:

   • A — one assignment
   • B — one evaluation of a Boolean (e.g., a comparison)
   • S — one addition or subtraction
   • M — one multiplication or division
   • P — one increment (e.g., ++)

2. Once you have an expression for the time required, based on a micro-analysis, you are asked to switch to a macro-analysis to get Big-Oh running time. Although it may be tempting to argue, "just use the highest power", in at least four cases you must give a careful mathematical argument (based on inequalities and algebra).

3. Reference: "Summation formulas" from Tripod

Exercise 1

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

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

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

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

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

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

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

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?

Exercise 9

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.

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

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

Exercise 11

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.