# Lab 14: Experiment 1

## Creating New n-Element Containers

### Files

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:

• 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.
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:

• 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

constant time, linear time, quadratic time
Back to the Lab Exercise  |  Forward to the Next Experiment