Directory: `lab14`

`initial.cpp`

implements this experiment.`Timer.h`

, and`Timer.doc`

implements the timer required by all experiments (there is no`Timer.cpp`

).

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

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

__Perform the
test__

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.)

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 ann-element`list`

? Justify your answer.

Question #14.1.2: How would you categorize the time it takes to create ann-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.

Back to the Lab Exercise | Forward to the Next Experiment

© 2003 by Prentice Hall. All rights reserved.

Report all errors to Jeremy D. Frens.