2

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:

  1. Why and how i-1 = -1 is defined?
  2. 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.
3

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.

  • Very helpful. I got the exact answer I was looking for. – zilcuanu Aug 10 '14 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.