3

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.

user1320353
  • 33
  • 4

1 Answers1

5

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)

MBo
  • 77,366
  • 5
  • 53
  • 86
  • Do you mean: k * (A + (A+A) + (A+2A) + ... + (A+(N-1)*A)) instead of: k * (A + (A+A) + (A+2A) + (A+(N-1)*A)) since there could be more terms in the middle? I got to that point but I couldn't simplify it, could you explain a bit how you simplified it down to: k * (A*N + A*N*(N-1)/2)? – user1320353 Apr 17 '12 at 13:50
  • Yes, of course, I missed " ...", corrected and added some words – MBo Apr 17 '12 at 15:20
  • No, If increment = n, then Cost = A*N + n*N*(N-1)/2 = O(N^2) asymptotically – MBo Apr 17 '12 at 16:11
  • isn't N the number of times your array grows? In my case I insert n elements, and we grow every 1000 elements, so shouldn't N = n/1000? – user1320353 Apr 17 '12 at 17:24
  • Yes, N is the number of times your array grows. If you insert n elements, then we grow every n elements too. N doesn't depend on n. – MBo Apr 17 '12 at 17:30
  • If everything is required to be stored in a single linear array, adding elements piecemeal leads to O(N^2) performance when adding a large number of items N. If one is allowed to use nested arrays, smaller expansions pose less of a problem (if nesting depth increases with N, all operations incur a per-item cost of O(lgN), but that time is absolute rather than amortized). – supercat Mar 04 '15 at 23:47