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/2011S/labs/code/analysis
There you will be able to access some precompiled 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 BigOh 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 BigOh 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 BigOh 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 BigOh 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 closedform for the value that will be
returned? (If not, you might want to consult [Weiss, Section 5.2].)
 What is the BigOh 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 BigOh 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 BigOh 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 BigOh 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 BigOh?
Remember, BigOh 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 loworder 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 upperright 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 upperright 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!)