Lab 14: Experiment 5

Prepending n Values to an Empty Container

Files

Directory: lab14

• prependN.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 prepend n values to the beginning of an existing container. As in Experiment #3, Perform the step consists of a loop that inserts n values. Also similar to Experiment #3, we do not consider the cost of creating our containers since we create empty containers.

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

Enter the results into a spreadsheet and graph the results.

The Analysis

Using the categories in Experiment #1 and your new graph, answer these questions:

Question #14.5.1: How would you categorize the time it takes to prepend n values to the beginning of a list? Justify your answer.

Question #14.5.2: How would you categorize the time it takes to prepend n values to the beginning of a vector? Justify your answer.

Let's take one last look behind the scenes.

The list

As we saw in Experiment #4, prepending a value to a list takes constant time. Just as in Experiment #3, when we do a constant-time operation n times, we end up with a linear-time operation.

The vector

In Experiment #3, our naive analysis suggested that appending n values should be a quadratic operation. But then we noticed that the costly size-equal-to-capacity case (tested in Experiment #2) is actually quite rare; more often we end up with a constant-time case. So appending n values turns out, on the whole, to be a linear-time operation.

It almost seems like we're set up the same way here. If we generalize from Experiment #3, we'd be inclined to say that prepending n is also a linear-time operation. But your graph should say something different.

While Experiment #4 says that the size-equal-to-capacity prepend is a linear-time operation (just like the append operation seen in Experiment #2), we haven't yet analyzed the case when the size is less than the capacity. This was the crucial observation in Experiment #3, and we need to do the analysis here.

Again, consider this vector:

To prepend a value to this vector, the vector follows these steps:

1. It copies the existing values one position to the right (starting from the right).
2. It writes the new value to the position whose index is 0.
3. It increments the size attribute.

Question #14.5.3: Using the vector above as a starting point, prepend the values 2 and 3 to the vector. Draw at least two pictures of the vector after each prepend, although you may find it helpful to draw the vector after each step of the algorithm.

Compare these steps with the steps listed in Experiment #3 for appending a value. Prepending a value to a vector starts with copying the existing values; that's a loop that takes as long as the size of the vector---a linear time operation! So even in the more common size-less-than-capacity case, prepending involves a linear-time operation. If we do a linear-time operation n times, we end up with a quadratic-time operation.