algorithm - Why is vector array doubled?

Question

Why does the classic implementation of Vector (ArrayList for Java people) double its internal array size on each expansion instead of tripling or quadrupling it?

Answer 1

When calculating the average time to insert into a vector, you need to allow for the non-growing inserts and the growing inserts.

Call the total number of operations to insert n items o_total, and the average o_average.

If you insert n items, and you grow by a factor of A as required, then there are o_total = n + ΣAⁱ [ 0 < i < 1 + ln_An ] operations. In the worst case you use 1/A of the allocated storage.

Intuitively, A = 2 means at worst you have o_total = 2n, so o_average is O(1), and the worst case you use 50% of the allocated storage.

For a larger A, you have a lower o_total, but more wasted storage.

For a smaller A, o_total is larger, but you don't waste so much storage. As long as it grows geometrically, it's still O(1) amortised insertion time, but the constant will get higher.

For growth factors 1.25 ( red ), 1.5 ( cyan ), 2 ( black ), 3 ( blue ) and 4 ( green ), these graphs show point and average size efficiency ( ratio of size/allocated space; more is better ) on the left and time efficiency ( ratio of insertions / operations; more is better ) on the right for inserting 400,000 items. 100% space efficiency is reached for all growth factors just prior to resizing; the case for A = 2 shows time efficiency between 25% and 50%, and space efficiency about 50%, which is good for most cases:

For runtimes such as Java, arrays are zero filled, so the number of operations to allocate is proportional to the size of the array. Taking account of this gives reduces the difference between the time efficiency estimates: