# Lab 14: Experiment 3

## Appending n Values to an Empty Container

### Files

Directory: `lab14`

### The Experiment

For this experiment, the test is to append n values to the end of an existing container. The `Perform the test` step consists of a loop that appends n values to the container.

Now, unlike Experiment #2, we do not have to consider the cost of creating our containers because we create empty containers. Yes, creating an empty container does take time, but this time is not dependant on n. Creating an empty container always takes the same amount of time. (You could always modify the program from Experiment #1 to verify this.)

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

Enter the results into a spreadsheet and graph the results.

### The Analysis

Use the categories from Experiment #1 to categorize your results:

Question #14.3.1: How would you categorize the time it takes to append n values to the end of a `list`? Justify your answer.

Question #14.3.2: How would you categorize the time it takes to append n values to the end of a `vector`? Justify your answer.

Let's look at the two containers we're experimenting with to establish our expectations.

#### The `list`

As we saw in Experiment #2, it takes constant time to append a value to a `list`. Since this experiment runs that operation n times, we'd expect the running time here to be a constant times n----linear time!

#### The `vector`

As we saw in Experiment #2, it takes linear time to append a value to a `vector` when the size and capacity are the same. If we do this n times, we end up with n*n work---quadratic time!

But, you're graph should not be quadratic. It's linear (or pretty close to it)! The numbers aren't wrong; our analysis is. The important phrase is "when the size and capacity are the same". That's the situation we had in Experiment #2. While this situation occurs sometimes while appending n values, it's still very, very infrequent. It's much more common to have a capacity greater than the size, and so the `vector` has some free space for new values.

In our analysis in Experiment #2, we ended with this picture:

If we add another element to this `vector`, the `vector` goes through these steps:

1. It stores the new value at the first open position in the array (i.e., use the size as an index).
2. It increments the size of `aVector`.

That's even simpler than appending a value to a `list`!

Question #14.3.3: Starting with the picture above, append the values `2` and `3` to the `vector`. Draw two pictures, one after each append.

If you analyze things further, doubling the array when allocating a new one (see the analysis in Experiment #2) saves us in the long run. The size-equal-to-capacity case turns out to be quite rare, and our `vector` ends up using the much simpler, constant-time case much more often. This is known as amortizing the cost; a `vector` spends a good deal of time in the size-equal-to-capacity occasionally to make the more common cases run much faster.

So, on the whole, appending to a `vector` turns out to appear to take constant time. Consequently, appending n items appears to take linear time.

## Terminology

amortize
Back to the Lab Exercise  |  Forward to the Next Experiment