How does the token method of amortized analysis work in this example?

Question

Below is the description of the answer to a question which says the following:

Design a data structure to support two operations for a dynamic multiset S of integers which allows duplicate values.

1. Insert operation for one element
2. Delete-larger-half(S) deletes the largest ceil(|S|/2) elements from S.
3. m insert and delete-larger-half operations run in O(m) time.
4. Also output the elements in O(|S|) time.

In answer unsorted array has been taken. I think delete-larger-half corresponds to deleting the |S|/2 elements with highest magnitude. Then how does deleting with median work unless there is n comparisons (i.e compare each element with the median). I suppose the amortized analysis is what is bringing out the complexity. I'm looking for an answer that can explain the token based amortized analysis by using the example in this question.

What I know already: Amortized analysis means doing some expensive work in previous steps which leads to worst case of a following step not happening as often. Every time the expensive step occurs, the probability of it happening again reduces more and more. On average it evens out giving a better amortized complexity. Example: implementing dynamic array which is probably what has been done in the solution linked below.

Link to solution: https://courses.csail.mit.edu/6.046/fall01/handouts/ps7sol.pdf

You use an unsorted array, so insert takes O(1) worst-case time. For DELETE-LARGER-HALF, you use the linear-time median algorithm to find the median, then you use PARTITION to partition the array around the median, then you delete the larger side of the partition in O(1) time. For the amortized analysis, insert each item with 2 tokens on it. When you perform a DELETE-LARGER-HALF operation, each item in the list pays 1 token for the operation. When you delete the larger half, the tokens on these items are redistributed on the remaining items. If each item on the list starts with 2 tokens, they each have one after the median finding, and then each item in the deleted half gives its token to one of the remaining items. Thus, there are always two tokens per item and we get constant amortized time.

I've not been able to understand the logic behind random assigning of token and taking it off.

In the answer, the insert has been assigned 2 tokens, the find median and partition take away 1 token total. And then deletion gives the 1 token. I understand that each time, delete-larger-half is called, the next delete-larger-half's cost reduces drastically but why exactly the values 2, 1, 1 have been chosen?

Answer 1

Then how does deleting with median work unless there is n comparisons (i.e compare each element with the median).

After partitioning (they assume Quicksort-style partitioning), you can just delete the last $\lceil |S| / 2 \rceil$ elements in the array.

Amortized analysis means doing some expensive work in previous steps which leads to worst case of a following step not happening as often. Every time the expensive step occurs, the probability of it happening again reduces more and more.

That is a useful intuition, but I feel a little bit besides the point.

Mainly, amortized analysis is about investigating the compound cost of sequences of operations. By dividing the sum by the number of operations we get what we call amortized cost for each operation.

I don't see a specification of such sequences in your problem statement so it may be ill-posed, unless the analysis goes through for all sequences.

So let us check. What is the worst that could happen? Well, probably a sequence of only DELETE-LARGER-HALF operations; consider $n$ elements and a sequence of $m = \lfloor \log_2 n \rfloor$ DELETE-LARGER-HALF operations (after this many, the set is almost empty). Since each operation has linear cost in the number of elements, the total cost then is $\Theta\bigl( \sum_{i=1}^{\log_2 m} 2^i \bigr) = \Theta(m)$ -- fits!

If we wanted to make this sequence more expensive by making individual summands larger, we would need to add INSERT operations. Say we wanted to increase one summand $2^i$ to $2^{i+1}$. We would have to add $2^i$ elements at cost $O(1)$ each, so the compound cost would increase by $2^{i+1}$ -- but $m$ would increase by $2^{i}$! Therefore, the amortized cost would only increase by a constant.

The core observation is this: if an element is to partake in making a DELETE-LARGER-HALF operation expensive (by being there), it has to be INSERTed first. Since DELETE-LARGER-HALF has linear cost, we can not add more than constant cost per element. In combination, this means we will get constant amortized time.

The tokens are a way to formalize this into a proof (which the part you quote does not quite manage to do). The way the tokens are set up and passed around, we see that the cost of any sequence of operations is in $\Theta$ of the total number of tokens we see. We can not possibly see more than $2m$ different tokens so we get an $O(m)$ bound on the compound cost or an $O(1)$ bound on the amortized cost.