Proof Hotlist amortized analysis is O(sqrt(n)) for Insert and Contain Operations - Hotlist Data Structure

Question

A hotlist is a data structure that has two arrays:

1. a sorted array size m, and
2. an unsorted array size sqrt m.

Initially m = 9 which means that the unsorted array can take up to 3 elements. But they are both empty, so n = 0. If the unsorted array is full (which also means that the sorted array is full), the unsorted gets sorted and then both arrays are merged into a new sorted list (merge step in merge-sort) with m’ = m + sqrt(m). A new unsorted array is allocated with the new size sqrt(m’).

I know that if we are to do a “contains” operation on the sorted array, it would be done by a binary search because the array is sorted. If the element x is not contained, then I would do a linear search in the unsorted array to look for it. But it’s of course slow, and would take O(sqrt(n)) time.

For the insert operation, it’s a bit complicated, because there are two cases:

1. The first array is not yet full. Then the value is appended to it. If the first (but not yet sorted) array has become full, then it gets sorted by merge-sort.

2. If the sorted array is already full. The new element is then inserted in the second array.

I want to show that both these operations, contain and insert, can be done amortized in O(sqrt(n)) time.

I tried using the accountant method. But I am not sure how much I have to pay per Insert, and how these merge steps have to be paid for. I know that sorting the second list would take O(sqrt(n)log(sqrt(n)) time and the merging of both would take n + sqrt(n) time which sums up to O(n) time. But this is slow. My idea is that merge takes cn time and every time before we merge there are sqrt(n) insert operations in the hotlist, which cost only O(1) each. So we try to save in every simple insert csqrt(n) in order to pay for the merge step. But I’m not sure how this can be showed using the accountant method. Or the potential method for example.