Hi,
This is about 'An amortized analysis of extendable arrays' from the book 'Data Structures and Algorithms in
Java' by Michael Goodrich and Roberto Tamassia. Here is the website -
http://as.wiley.com/WileyCDA/WileyTitle/productCd-EHEP001656.html
First I'm not sure if I'm violating copyrights by asking my question here but the book does not have any copyright information. And also this book is used as a text book in many a computer science university courses, so I believe it should be fine. Correct me, if it is otherwise.
Ok, here is my question.
The current context is this - we are using a fixed capacity array to implement an ArrayList ( like the one we have in java.util.ArrayList ). When the capacity is reached, and an insert/add is done, a new array of double the size of the previous array is created and elements are copied into the new array. We are analyzing the performance of these add operations using these extendable arrays.
The authors' state the following ( copying as is ).
"As a shorthand notation, let us refer to the insertion of an element to be the last element in an array list as a push operation. Using an algorithmic design
pattern called amortization, we can show that performing a sequence of such push operations on an array list implemented with an extendable array is actually quite efficient. To perform an amortized analysis, we use an accounting technique where we view the computer as a coin-operated appliance that requires the payment of one cyber-dollar for a constant amount of computing time. When an operation is executed, we should have enough cyber-dollars available in our current "bank account" to pay for that operation's running time. Thus, the total amount of cyber-dollars spent for any computation will be proportional to the total time spent on that computation. The beauty of using this analysis method is that we can overcharge some operations in order to save up cyber-dollars to pay for others."
I have understood the above parts. After this the authors' are proving the proposition as follows.
"Proposition 6.2: Let S be an array list implemented by means of an extendable array with initial length one. The total time to perform a series of n push operations in S, starting from S being empty is O(n).
Justification:
Let us assume that one cyber-dollar is enough to pay for the execution of each push operation in S, excluding the time spent for growing the array. Also, let us assume that growing the array from size k to size 2k requires k cyber-dollars for the time spent copying the elements.
We shall charge each push operation three cyber-dollars. Thus, we overcharge each push operation that does not cause an overflow by two cyber-dollars. Think of the two cyber-dollars profited in an insertion that does not grow the array as being "stored" at the element inserted. An overflow occurs when the array list S has 2i elements, for some integer i ≥ 0, and the size of the array used by the array list representing S is 2i. Thus, doubling the size of the array will require 2i cyber-dollars. Fortunately, these cyber-dollars can be found at the elements stored in cells 2i−1 through 2i − 1. (See Figure 6.4.) Note that the previous overflow occurred when the number of elements became larger than 2i−1 for the first time, and thus the cyber-dollars stored in cells 2i−1 through 2i − 1 were not previously spent. Therefore, we have a valid amortization scheme in which each operation is charged three cyber-dollars and all the computing time is paid for. That is, we can pay for the execution of n push operations using 3n cyber-dollars. In other words, the amortized running time of each push operation is O(1); hence, the total running time of n push operations is O(n)".
This is what I have not understood. The parts in bold ( they are my own edits ) specifically. Could you please help me understand what the authors are trying to say that we charge each push operation as one cyber dollar first, and then three cyber dollars and how are we saving two cyber dollars. I know I should ask this to the authors, but the publisher does not have 'ask a question' sort of a thing. Besides I believe many of you here wouldn't mind helping me on this one.
Thanks so much in advance for reading it through and for spending time on it ( I know it's quite big- sorry about that ). I've been trying to understand this for the last one hour - no go still.
Chan.