Draw pictures illustrating each of the major steps in the algorithms for functions insert(p,e), insertFront(e), and insertBack(e)

Question:

Draw pictures illustrating each of the major steps in the algorithms for functions insert(p,e), insertFront(e), and insertBack(e) of Code Fragment 6.5.


Data from in Code Fragment 6.5

Themember functions reserve and insert for class ArrayVector. In terms of efficiency, this array replacement strategy might, at first, seem rather slow. After all, performing just one array replacement required by an element insertion takes O(n) time, which is not very good. Notice, however, that, after we perform an array replacement, our new array allows us to add n new elements to the vector before the array must be replaced again.
This simple observation allows us to show that the running time of a series of operations performed on an initially empty vector is proportional to the total number of elements added. As a shorthand notation, let us refer to the insertion of an element meant to be the last element in a vector as a “push” operation. Using a design pattern called amortization, we show below that performing a sequence of push operations on a vector implemented with an extendable array is quite efficient.

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question

Data Structures And Algorithms In C++

ISBN: 9780470383278

2nd Edition

Authors: Michael T. Goodrich, Roberto Tamassia, David M. Mount

Question Posted: