Lab 14: Experiment 3

Appending n Values to an Empty Container

Files

Directory: lab14

• appendN.cpp implements this experiment.
• Timer.h, and Timer.doc implements the timer required by all experiments (there is no Timer.cpp).

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