Assume that you run one of the executables for various N values, time them and record a table of values such as the following:

N value | Time in seconds |

4 | 4 |

8 | 12 |

16 | 40 |

32 | 144 |

64 | 544 |

Say you decide to test these values to see if they're closer to O(N) or to O(N^{2}).
If they're O(N) then for large enough N they should obey Time = b*N where b is some constant (whose
exact value is unimportant).
Then the ratio of two times should obey Time1/Time2 = b*N1/b*N2 = N1/N2. For example we
should have Time(N=32)/Time(N=16) = 32/16 = 2, whereas the actual ratio from the table
you've collected is 144/40 = 3.6, which is a lot larger than 2.

So it appears as if the complexity is worse than O(N) so you try O(N^{2}).
In this case you should eventually see Time1/Time2 = b*N1^{2}/b*N2^{2}
= N1^{2}/N2^{2}. For the case we looked at before, comparing N=32 to
N=16 gave us a ratio of 3.6 whereas 32^{2}/16^{2} = (32/16)^{2}
= 2^{2} = 4. Now 3.6 is a lot closer to 4 than 2 is to 4. If you're patient enough
to run the N=64 case and wait for about 9 minutes for it to complete, the ratio of
the two times is 3.8 or so, even closer to 4.

In doing all these computations, you might want to add a few columns to your table and fill in some ratios. Also note that it is not necessary to compare the ratios of times for N values that are just a factor of 2 apart. In fact, for O(NlgN) behavior it is better to compare times for N values that are 4x or 8x or even 16x apart to see the difference between O(N) and O(NlgN) behavior. But of course don't use such small values of N that an interfering term could be deceiving you.

In conclusion, in this example we've found that as N gets large,
the ratio of successive times for doubled
N values is approaching 4, which would suggest O(N^{2}) behavior.

Now I'll reveal the actual function that was used to create the values above. It is
Time = (1/8)*(N^{2} + 4*N). This function eventually is dominated by the N^{2}
term so it truly is O(N^{2}). But for small values of N the linear 4*N factor contributes significantly. In fact,
the ratio of the two contributions is N^{2}/(4*N) = N/4, so for N=4 they contribute
equally, whereas for N = 64, the second term is only 1/16 the first, or about 6% of the dominate
term.

- You should turn in a hardcopy of your tables of all the timing experiments and the inferences for each of the 6 programs.
- At the top of the first page put your name, your ID number, your email address, the date, "COM1201 Spring 2000", and "Machine Problem 1". If you attach additional pages, put your name on each page, at a minimum. Only hardcopy will be accepted.
- All homework should be handed in to Professor Futrelle by the beginning of class on Tuesday, May 2nd.
- All late homework should be handed in to Ms. Zheng, Room 23CN, or in her mailbox in CCS headquarters, Room 161CN. Grade is reduced 10% x number of classes late it is handed in.
- The percent credit for this lab towards your grade will be worked out in relation to the total number of assignments and labs that are ultimately assigned for this course.

I think you'll find this lab interesting and instructive and not that difficult or time-consuming to do.