Resizing an array by a non-constant, continually

Question

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! :)

Answer 1

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).

Answer 2

This can be easily shown using the Accounting Method. Consider an array of size k+sqrt(k) such that the first k entries are occupied and the rest sqrt(k) are empty. Let us make Insert-Last operation draft sqrt(k)+2 coins: One will be used to pay for insertion while the rest (sqrt(k)+1 coins) will be deposited and used for credit. From here, execute Insert-Last sqrt(k) times. We shall then have k+sqrt(k) credit coins: in total we had drafted k+2sqrt(k) coins, sqrt(k) of which we used for paying for the insertions. Hence, we won't need to pay for the resizing of the array. As soon as the array gets full, we would be able to utilize our k+sqrt(k) credit coins and pay for the resizing operation. Since k = ?(n), each Insert-Last operation drafts sqrt(k)+2 = O(sqrt(k)) = O(sqrt(n)) coins and thus takes O(sqrt(n)) amortized.