Runtime of a dynamic array that increase by a constant instead of doubling
data-structures, dynamic-tables
Solution
Let's initial size is A, and increment is A too, and we have N growing steps. Every step requires k*Size elementary operations to copy elements (and to clear memory, if needed).
Cost = k * (A + (A+A) + (A+2A) + ... + (A+(N-1)A)) = k(A*N +A*(1 + 2 + 3 +... + (N-1))) = k * (A*N + A*N*(N-1)/2) = O(N^2 * A) = O(N^2) (assuming A is constant)
1 + 2 + 3 +... + (N-1) is sum of arithmetic progression
P.S. Doubling the array costs O(N)
Problem
I just finished an exam, and one of the question was in summary: Given an empty array of size 1000, what is the amortized cost of inserting n elements into the array? When the array is full, instead of doubling the array, we increase it by 1000 and copy all the elements into the new array as you would for dynamic tables. I answered O(n) but I'm not at all sure of my answer. I know the amortized run-time of a doubling dynamic table is 2, but I could not find much information about dynamic-tables that grow a constant size.