appendN.cppimplements this experiment.
Timer.docimplements the timer required by all experiments (there is no
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.
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.
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!
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
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
goes through these steps:
That's even simpler than appending a value to a
Question #14.3.3: Starting with the picture above, append the values
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
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.