I was reading a book on Algorithm Analysis by Micheal T Goodrich. I came across amortization technique and I got struck in understanding the proof of theorem. I am putting the theorem and the proof and the part that I need some more explanation. Please help me:
Theorem: A series of n operations on an initially empty clearable table implemented with an array takes O(n) time
Definition of clearable table: This Abstract data type stores table of elements, which can be accessed by their index in the table. In addition this ADT supports the following two methods:
add(e): Add the element e to the next available cell in the table.
clear : Empty the table by removing all its elements.
Proof: Let M0….,Mn-1 be the series of operations performed on S, and let Mi0,….,Mik-1 be the clear operations within the series. We then have,
0<= i0 < …. < i k-1 <= n-1.
Let us also define i-1 = -1. The running time of operation Mij (a clear operation) is O(ij – ij-1), because at most ij – ij-1 -1 elements could have been added into the table (using the add operation) since the previous clear operation Mij-1 or since the beginning of the series.
Question:
- Why and how i-1 = -1 is defined?
- I did not understand “because at most ij – ij-1 -1 elements could have been added into the table (using the add operation) since the previous clear operation Mij-1 or since the beginning of the series”. Please explain me more on this statement on why -1 came into the picture.
I’ll start with your second question. That -1 comes from the fact, that both ij and ij-1 are clear operations, you want to count only the add operations in between, so you do not have to count the left and right values. (For example there are 3 values between 3 and 7: 4, 5, 6.)
The answer for your first question: because it is before the first element and it works well with the quoted text. (For example assume the first clear is at index 2; between i-1=-1 and i0=2, there are 2 integers: 0 and 1, so the formula of ij-ij-1-1 = 2-(-1)-1=2 still works well.) You could use a smaller number as well, but that would be more confusing.
1