A question on resizing dynamic arrays (as part of an ArrayList ADT) has me stumped.
The text sets up a scenario where elements are added to the end of an array. When the array reaches its capacity it is doubled in size. The new larger array is initialized with the elements of the old array. An amortized analysis of the process gives a complexity of O(n).
Then the following question is asked:
When the array of capacity N is full, instead of copying the N elements into an array of capacity 2N, they are copied into an array with N/4 additional cells, i.e an array of capacity (N + N/4). Show that performing a sequence of n additions to the array still runs in O(n).
Any tips, help on how to approach this question are much appreciated. I don't know how to handle the fact that an array at full capacity is being increased in size by a fraction of its current size, rather than a multiple of its current size.
The successive copies have size N, N(5/4), N(5/4)^2, ...
Consequently, after K copies, the total cost of copying is
sum(i=0,K-1){ N(5/4)^i }
At that point the array has size N(5/4)^(K-1).
So all that's left is to show that
O( [ sum(i=0,K-1){ N(5/4)^i } ] / [ N(5/4)^(K-1) ] ) = O(1) .
In words, this is the total cost of copying per array element, which is amortized cost.
Showing the equation is true is pretty straightforward, and the logic is much the same as showing the similar relation for doubling:
O( [ sum(i=0,K-1){ N(2)^i } ] / [ N(2)^(K-1) ] )
I won't take away your fun.