Directory: `lab14`

`prependN.cpp`

implements this experiment.`Timer.h`

, and`Timer.doc`

implements the timer required by all experiments (there is no`Timer.cpp`

).

For this experiment, the test is to prepend *n* values to the
beginning of an existing container. As in Experiment #3,
consists of a loop that inserts

Compile and run 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 #14.5.1: How would you categorize the time it takes to prependnvalues to the beginning of a`list`

? Justify your answer.

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

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

Back to the Lab Exercise

© 2003 by Prentice Hall. All rights reserved.

Report all errors to Jeremy D. Frens.