Lab 13: Experiment 1

Creating New n-Element Containers

Files

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

The Experiment

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

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

All we do is allocate new containers; Perform the test is left empty.

Creating a new container does take time; there's some work involved — perhaps a lot if the container is initialized to some rather large size. Because we'll be creating these containers for the other tests, we want to find out how costly it is to construct an n-element container.

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

Record your results in a spreadsheet and graph them as described in the main lab exercise.

Analysis

To measure the performance of an operation we determine how long it takes for a data set of size n as n changes. We would probably expect that a larger input — i.e., a larger n — will result in execution taking longer. But how much longer? Sometimes n plays no significant role; other times it plays a very important role.

Here are three different categories of performance measures that are used in computing:

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. In computing, this constant-time performance is describe by saying the operation is O(1).

Linear time. The time to perform the operation varies as c·n, where c is some constant. Such linear performance is described by saying the operation is O(n). The graph of a linear time operation is a straight line, increasing as n increases.

Quadratic time. The operation is O(n²). The time to perform the operation is proportional to n² — that is, c·n² where c is some constant. The graph of a quadratic time operation is parabolic.

There are additional categories (e.g., logarithmic, cubic, exponential, factorial, etc.), but these three are all that we will see in this exercise.

Use these definitions to do some categorization of your results:

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

Question #13.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.

Back to the Lab Exercise | Forward to the Next Experiment

Report errors to Larry Nyhoff (nyhl@cs.calvin.edu)