# Amortized time of insertion into an Array list

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

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.

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