Lab 14: Experiment 1

Creating New n-Element Containers


Directory: lab14

The Experiment

For this experiment, the test is to create and (implicitly) initialize the 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 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:

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 #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:

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.


constant time, linear time, quadratic time
Back to the Lab Exercise  |  Forward to the Next Experiment
© 2003 by Prentice Hall. All rights reserved.
Report all errors to Jeremy D. Frens.