## Lab 06: Execution times

## Learning Goals

After this lab you should be able to agree with each of the following statements.

I can evaluate the efficiency of algorithms:

- I understand the correlation between input and running time for different program structures
- I can use big-o-notation to describe the running time of algorithms
- I can calculate the running time of algorithms by adding up running times of different structures
- I can compare running times based on their running time in big-o-notation

## Pre-Lab

* P1.* Programs A and B are analyzed and are found to have worst-case running times no greater than $150 N \log N$ and $N^2$, respectively. Answer the following questions, if possible:

a) Which program has the better guarantee on the running time for large values of $N (N > 10 000)$?

b) Which program has the better guarantee on the running time for small values of $N (N < 100)$?

c) Which program will run faster on average for $N = 1000$?

d) Is it possible that program B will run faster than program A on all possible inputs?

* P2.* An algorithm takes 0.5 ms for input size 100. How long will it take for input size 500 if the running time is the following:

a) linear

b) $O(N \log N)$

c) quadratic

d) 4. cubic

* P3.* An algorithm takes 0.5 ms for input size 100. How large a problem can be solved in 1 min if the running time is the following:

a) linear

b) $O(N \log N)$

c) quadratic

d) cubic

* P4.* Order the following functions by growth rate, and indicate which, if any, grow at the same rate.:

- $N$
- $\sqrt{N}$
- $N^{1.5}$
- $N^2$
- $N \log N$
- $N \log \log N$
- $N \log^2 N$
- $N \log (N^2)$
- $\frac{2}{N}$
- $2N$
- $\frac{2N}{2}$
- $37$
- $N^3$
- $N^2 \log N$

## Assignment

### Part 1: Analysis of Algorithms

For each of the following seven program fragments, do the following:

- Do a Big-Oh analysis of the running time.
- Implement the code in a simple main class and run it for several interesting values of N.

#### Code Fragments

```
// Fragment #1
for ( int i = 0; i < n; i ++)
sum++;
// Fragment #2
for ( int i = 0; i < n; i ++)
for ( int j = 0; j < n; j ++)
sum++;
// Fragment #3
for ( int i = 0; i < n; i ++)
for ( int j = i; j < n; j ++)
sum++;
// Fragment #4
for ( int i = 0; i < n; i ++)
sum ++;
for ( int j = 0; j < n; j ++)
sum ++;
// Fragment #5
for ( int i = 0; i < n; i ++)
for ( int j = 0; j < n*n; j ++)
sum++;
// Fragment #6
for ( int i = 0; i < n; i ++)
for ( int j = 0; j < i; j ++)
sum++;
// Fragment #7
for ( int i = 1; i < n; i ++)
for ( int j = 0; j < n*n; j ++)
if (j % i == 0)
for (int k = 0; k < j; k++)
sum++;
// Fragment #8
int i = n;
while (i > 1) {
i = i / 2;
sum++;
}
```

### Part 2: Prime Numbers

A *prime number* has no factors besides 1 and itself. Do the following:

Write a simple method

`public static bool isPrime (int n) {...}`

to determine if a positive integer N is prime.In terms of N, what is the worst-case running time of your program?

Let B equal the number of bits in the binary representation of N. What is relationship between B and N?

In terms of B, what is the worst-case running time of your program?

Compare the running times needed to determine if a 20-bit number and a 40-bit number are prime by running 100 examples of each through your program.

### For the bored:

The Sieve of Eratosthenes is a method used to compute all primes less than N. Begin by making a table of integers 2 to N.
Find the smallest integer i that is not crossed out - i is prime! (you might want to print it here to see the progress, but really you shouln’t mix output within the algorithm) - and cross out all multiples of i (i , 2i , 3i , ….)
Terminate when i is greater than the square root of N. The running time has been shown to be O (N log log N). Write a program to implement the Sieve and verify that the running time is as claimed. If you are *really* bored, animate this with a GUI like on the Wikipedia!

## Lab Report / What to turn in

All info on the lab reports can be found on the Labs page.

Also answer the following questions in your report.

Additional questions for part 1:

- Which are interesting values for N?
- Compare your analysis with the actual number of steps (i.e. the value of sum after the loop).