On 09/04/2008, Stefan Dösinger <[EMAIL PROTECTED]> 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.
