Use amortized analysis to give a bound on the worst-case running time of a sequence of n operations on the following data structure X:

1) INSERT on X with n elements takes time log n and increases X's potential by log n.

2) FIND on X with n elements takes time k + where k is the number of elements examined. It decreases X's potential by k - 3.

3) REMOVE on X with n elements takes time log n and increases the potential by 3.

The data structure is initially empty. The potential of X is always 0 and is 0 if X is empty.

Transcribed image text