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.
- 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.