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".

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Some list implementations use the golden ratio as growth rate $\endgroup$
    – matheussilvapb
    Oct 31, 2017 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, 2017 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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