2
$\begingroup$

In Elements of Programming Interviews in Python by Aziz, Lee and Prakash, they state on page 41:

Insertion into a full array can be handled by resizing, i.e., allocating a new array with additional memory and copying over the entries from the original array. This increases the worst-case time of insertion, but if the new array has, for example, a constant factor larger than the original array, the average time for insertion is constant since resizing is infrequent.

I grasp the concept of amortization that seems to be implied here, yet they seem to imply that in other cases, a newly allocated array could possess a constant factor smaller than the original array. Is that so? What does "constant factor" mean in this particular context? I'm having trouble understanding what's being said here.

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Apr 21 at 12:16
5
$\begingroup$

That's probably a typo or poor wording -- in the quote, "has" should be "is".

$\endgroup$
3
$\begingroup$

This approach suggest to pick any constant factor $k>1$ and use that whenever one needs to reallocate the array. That is, each time the array becomes full and has $n$ elements, a new array of size $k\cdot n$ is allocated, and data is copied from the old array.

It is important here to multiply the size by a constant $k$ rather than, say, adding a fixed amount of additional entries (moving from $n$ to $n+k$) to achieve a better amortized complexity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.