I’d like to perform amortized analysis of a dynamic array: When we perform a sequence of n insertions, whenever an array of size k fills up, we reallocate an array of size k sqrt(k), and copy the existing k values into the new array.

I’m new to amortized analysis and this is a problem I have yet to encounter, as we resize the array each time by a different non-constant value. (newSize=prevSize sqrt(prevSize))

The total cost should be Θ(n*sqrt(n)), thus Θ(sqrt(n)) per operation.

I realize that whenever k >= c^2 for some constant c, then our array grows by c. Let’s start off with an array of size k=1 (and assume n is large enough, for the sake of this example). After n insertions, we get the following sum of the total cost of the insertions copies:

1 1(=k) 1 2(=k) 1 3(=k) 1 4(=k) 2 6(=k) 2 8(=k) 2 10(=k) 3 13(=k) 3 16(=k) 4 20(=k) 4 24 4 28 5 33 5 38 6 44 6 50 7… n

I am seeing the pattern, but I can’t seem to be able to compute the bounds. I’m trying to use all kinds of amortized analysis methods to bound this aggregated sum. Let’s consider the accounting method for example, then I thought I needed round([k sqrt(k)]\sqrt(k)) or simply round(sqrt(k) 1) coins per insertion, but it doesn’t add up.

I’d love to get your help, in trying to properly find the upper and lower sqrt(n) bound.

Thank you very much! :)

CodePudding user response：

The easiest way is to lump together each resize operation with the inserts that follow it before the next resize.

The cost of each is lump is O(k sqrt(k)), and each lump consists of O(sqrt(k)) operations, so the cost per operations is O( (k k^0.5)/k^0.5) = O(k^0.5 1) = O(k^0.5)

Of course you want an answer in terms if n, but since k(n) is in Θ(n), O(k^0.5) = O(N^0.5).

CodePudding user response：

So answer the question in WhatsApp group