Lab 14: Experiment 1

Creating New n-Element Containers

Files

Directory: lab14

• initial.cpp implements this experiment.
• Timer.h, and Timer.doc implements the timer required by all experiments (there is no Timer.cpp).

The Experiment

For this experiment, the test is to create and (implicitly) initialize the containers:

list<int> theList(n);
vector<int> theVector(n);

Creating a new container isn't exactly free; there's some work that has to go into it---perhaps a lot of work if the container is initialized to some rather large size. Since we'll create these containers for the other tests, we should first figure out how costly it is to create an n-element container.

Compile and run the program on the sample range of n.

Enter the results into a spreadsheet and graph the results. Each graph you create should plot one line for the list results and another line for the vector results. The horizontal axis plots the various values for n; the vertical axis is the time it takes to do the operation. (This applies to all of the graphs for all of the experiments.)

The Analysis

Computer scientists categorize the time to perform an operation based on how long that operation takes depending on the value of n, the size of the input. Typically, we expect that a larger input (i.e., a larger n) results in a execution that takes longer. But how much longer? Sometimes n plays no significant role; other times it plays a very, very important role.

Here are three different categories that we'll define informally:

• Constant time. The time to perform the operation remains the same, regardless of the value of n. The graph of a constant time operation is a flat line, parallel to the n-axis.
• Linear time. The time to perform the operation is directly proportional to n---describable as c*n, where c is some constant. The graph of a linear time operation is a straight line, increasing as n increases.
• Quadratic time. The time to perform the operation is proportional to n^2---describable as c*n^2, where c is some constant. The graph of a quadratic time operation is a curve that rises as n increases, and rises faster as n increases. If you hold a straight edge to the graph, the graph will noticeably curve away from it.

Use these definitions to do some categorization of your results:

Question #14.1.1: How would you categorize the time it takes to create an n-element list? Justify your answer.

Question #14.1.2: How would you categorize the time it takes to create an n-element vector? Justify your answer.

Justification for your categories should describe the graph:

• It's a straight line, parallel to the n-axis.
• It's a straight line, increasing with n.
• It's a curve, increasing with n.

In later experiments we'll explore the results from this experiment; the primary purpose of this experiment is to establish a base-line for those other experiments.

Terminology