1/22/2024
Amortize method when increasing array size on stack implementation
There are two ways of implementing a stack: using an array or a linked list. Using the array method is faster, but the only downside is we don't know the size of the array beforehand. So, we increase the array's size each time we add another item. It costs N^2/2 times because each time we increase, we need to add N items from an old array to a new array (that has the size double the old array).
We can improve by doubling the array's size each time it is filled. It is like adding 1 more slot each time we add 1 more item, but we wait until the last minute and add all of them together. So, instead of accessing the array once each time we add, we access it twice, making the running time O of N, not N square.