prependN.cpp
implements this experiment.Timer.h
, and Timer.txt
implement
the timer required by all experiments (there is no Timer.cpp
).For this experiment, the test is to prepend n values at the
front 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 execute the program on the sample range of n.
Enter the results into a spreadsheet and graph the results.
Using the categories in Experiment #1 and your new graph, answer these questions:
Question #13.5.1: How would you categorize the time it takes to prepend n
values to the front of a list
? Justify your answer.
Question #13.5.2: How would you categorize the time it takes to prepend n
values to the front of a vector
? Justify your answer.
Let's take one last look behind the scenes.
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.
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 have the same situation. 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 indicate something different.
Although we found in Experiment #4 that the size-equal-to-capacityprepend is a linear-time operation (just like the append operation in Experiment #2), we haven't yet analyzed the case when the size is less than the capacity, which was the immportant observation in Experiment #3.
So, once again consider this vector
:
To prepend a value to this vector
, the vector
follows
these steps:
Question #13.5.3: Using thevector
above as a starting point, prepend the values2
and3
to thevector
. Draw at least two pictures of thevector
after each prepend, although you may find it helpful to draw thevector
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.