Info2: Exercise 05: 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 N2, 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
square root of N
N1.5
N2
N log N
N log log N
N log2 N
N log (N2)
2/N
2N
2N/2
37
N3
N2 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++;

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.
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).

Additional questions for part 2:

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?
Present the results of your experiment