Why is it common practice to double the capacity of an array when fully loaded?

Question

I noticed that very often (especially in interviews and homework) a dynamic array is used; as a rule, I see a question formulated as something like:

Implement an array in which doubles when full

Or something very similar. They almost always (in my experience) explicitly use the word double , and not the more general

Implement an array that increments when full

My question is: why double? I understand why it would be a bad idea to use constant value (thanks to this question ), but it seems that it makes sense to use a larger number than a double; why not triple the capacity, or increase it four times, or a square?

To be clear, I am not asking how to double the capacity of the array, I ask why doubling is an agreement.

Answer 1

Yes, this is a common practice.

Doubling is a good way to manage memory. Heap management algorithms are often based on the classic Buddy System, an easy way to deal with addressing and pooling and other problems. Knowing this, it’s good to stick with a multiple of 2 when dealing with distribution (although there are hybrid algorithms like the slab distributor to help with fragmentation, so this is not as important as it used to be several).

Knut covers it in one of his books, but I forgot the name.

See http://en.wikipedia.org/wiki/Buddy_memory_allocation

Another reason to double the size of the array is the cost of addition. You do not want each Add () operation to cause a redistribution call. If you filled N slots, there is a chance that you will need several multiple Ns anyway, the story will be a good indicator of future needs, so the object should "finish" to the next size of the arena. When doubling, the redistribution frequency falls logarithmically (Log N). Doubling is just the most convenient set (being the smallest integer factor, it is more memory efficient than 3 * N or 4 * N, plus it tends to closely monitor heap memory management models).

Answer 2

The reason for doubling is that he repeatedly adds an element to the depreciated transaction O(1) . In other words, adding n elements takes O(n) .

More precisely, magnification by any multiplicative factor achieves this, but doubling is a common choice. I saw other options, for example, in a magnification of 1.5 .