`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,
consists of a loop that inserts

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 prependnvalues to the front of a`list`

? Justify your answer.

Question #13.5.2: How would you categorize the time it takes to prependnvalues 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:

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

Question #13.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.

Back to the Lab Exercise

Report errors to Larry Nyhoff (nyhl@cs.calvin.edu)