Confusion in understanding the theorem on Amortization

Question

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 M₀....,M_n-1 be the series of operations performed on S, and let M_i0,....,M_ik-1 be the clear operations within the series. We then have,

0<= i₀ < .... < i _k-1 <= n-1.

Let us also define i_-1 = -1. The running time of operation M_ij (a clear operation) is O(i_j - i_j-1), because at most i_j - i_j-1 -1 elements could have been added into the table (using the add operation) since the previous clear operation M_ij-1 or since the beginning of the series.

Question:

1. Why and how i_-1 = -1 is defined?
2. I did not understand "because at most i_j - i_j-1 -1 elements could have been added into the table (using the add operation) since the previous clear operation M_ij-1 or since the beginning of the series". Please explain me more on this statement on why -1 came into the picture.

Answer 1

I'll start with your second question. That -1 comes from the fact, that both i_j and i_j-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 i₀=2, there are 2 integers: 0 and 1, so the formula of i_j-i_j-1-1 = 2-(-1)-1=2 still works well.) You could use a smaller number as well, but that would be more confusing.