Recently, I encountered a question about a data structure similar to a dynamic array. When you push a new element to a dynamic array (e.g. std::vector in C++ and ArrayList in java) and if it doesn’t have anymore storage, a reallocation will occur.
I remember last time when I was 2nd year student, a very 1st book I read about game engine programming told me how to dynamically increase the storage of dynamic array by increasing its size by a fixed amount (example: increase storage size by 5 elements, hence you are allowed to push 5 more elements before next resize, and so on).
I kept adhering to this implementation for a while until at some point, I realized it is not the most efficient way of resizing the array. Actually I was told it is that way, and hadn’t really thought of why. So let’s analyse its performance complexity today.
Le Hoang Quyen's homepage 