On 09/04/2008, Stefan Dösinger stefan@codeweavers.com wrote:
You usually grow the memory by a factor of the old size because this reduces the number of needed grows. So growing the stack is an O(log(n)) instead of O(n), which is a huge difference.
No, the amortized time per push is O(1). The realloc becomes more expensive as the array gets larger.
The drawback is that you have potentially more wasted memory. I don't know what the theory says to that though. The amount of wasted memory is always smaller than the amount of used memory at least if you double the size and smaller if you grow it by 1/2 of the existing size, ...
On average the percentage of wasted memory is (factor - 1) / 2. You make a trade of between memory usage and run time when picking the factor.