COM1201 Lab/Machine-Problem Assignment #1, updated 4/12/2000

Run-Time experiments to estimate algorithm complexity

Labs of Wednesday, April 12th, 2:50 or 4:05pm

DUE DATE: Tuesday April 18th



Getting Started

First, download all the files listed above in the Files section by simply clicking each link, and save them onto your Windows Desktop or some folder you've set up for them. Better than that, be at one of the labs Wednesday and Ms. Zheng has the executables on a floppy so you can copy them to your hard drive to use them and copy them to your own floppy if you'd like. The programs can be run by double clicking on the icons.

The Assignment

The assignment is to determine the time complexity (in  "Big Oh" notation, e.g., O(N) ) of each of the six programs by running them with different values of input (N) and noting the time taken for the completion of the program. A table with the values of N and the corresponding time taken should be constructed for each of the programs and an estimate of the complexity of each of the program should be made from the tables. A sufficient number of runs at appropriate N values should be made so that the true time complexity of the programs is discovered.

How to do the computations

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(N2). 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(N2). In this case you should eventually see Time1/Time2 = b*N12/b*N22 = N12/N22. For the case we looked at before, comparing N=32 to N=16 gave us a ratio of 3.6 whereas 322/162 = (32/16)2 = 22 = 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(N2) behavior.

Now I'll reveal the actual function that was used to create the values above. It is Time = (1/8)*(N2 + 4*N). This function eventually is dominated by the N2 term so it truly is O(N2). But for small values of N the linear 4*N factor contributes significantly. In fact, the ratio of the two contributions is N2/(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.

What to turn in

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