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.
- Insert operation for one element
- Delete-larger-half(S) deletes the largest ceil(|S|/2) elements from S.
- m insert and delete-larger-half operations run in O(m) time.
- 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?