Amortized Analysis of Binary Counter and Dynamic Table together


Let m ≥ 2 be a fixed positive integer. Consider the following ADT. A state of the ADT is an m-tuple of integers (v1, v2, . . . , v_m). The ADT supports two operations:

• Increment(i) which increases the value of vi by 1.

• Max returns an index of the maximum value, that is it returns an i such that vi ≥ vj for all j.

I am designing a data structure for this ADT as a dynamic sized table Ti. Each entry of Ti stores single bit of vi. This allows each component to grow arbitrarily large because we can resize the table to get longer and longer as value grows.

Now, Suppose the Algorithm for Max is :

Max res ← 1 for i ← 2..m if (number represented in Ti) > (number represented in Tres) then res ← i end if end for return res end Max 

Now, Given a sequence of s operations and initial state (0,0,0,0..0). I want to do amortized analysis of this case and find the total time and amortized time.