hverbeet at gmail.com
Wed Apr 9 15:41:25 CDT 2008
On 09/04/2008, Stefan Dösinger <stefan at 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
More information about the wine-devel