0
$\begingroup$

According to Amortized time cost of insertion into an Array list,

A dynamically resizing array list will resize when the number of elements reaches a power of two. So, after n elements inserted, we've resized at sizes 1, 2, 4, ... , n.

Can anyone kindly explain me the logic of this? If we consider the n(number of elements)=7 then we resize array at sizes 1,2,4 but according to above statement "1,2,4....7".

$\endgroup$
4
$\begingroup$

The question might be a little misleading.

So, after n elements inserted, we've resized at sizes 1, 2, 4, ... , n.

This is only true if $n = 2^k$ for some $k \in \mathbb{N}$, because for a growth factor of 2, we only need to resize when $n$ is a power of 2.

So in your case we would only resize at 1, 2, 4. Not 7.


You should keep in mind this only applies to a growth factor of 2. We could change the growth factor however we wish. For example we set the growth factor to 3. Then we resize at powers of 3; $\{1, 3, 9, \dots 3^k\}$. You can still use the same analysis procedure to get a constant amortized time though.

$\endgroup$
  • $\begingroup$ Some list implementations use the golden ratio as growth rate $\endgroup$ – matheussilvapb Oct 31 '17 at 11:07
  • $\begingroup$ @matheussilvapb, yes that could also be the case. You must then either assume the lower or upper bound $\lfloor \phi^k \rceil$. $\endgroup$ – ryan Nov 1 '17 at 0:44

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.