Chapter 16, Problem 19RE

Explanation of Solution

Sequence of addLast and removeLast calls having O(1) efficiency:

The O(1) efficiency of any sequence of addLast and removeLast calls could be shown in the following way:

• In the case of addLast method, $2 must be charged.
  • Out of that, $1 must be spent on moving the value to be added at the end of the array.
  • The remaining $1 should be put in the bank.
  • On the occasion of reallocation, “n” elements must be copied to the array that is twice as large...