We're given the algorithm which uses stack in order to store data (stack is implemented via an array). When the stack is full the algorithm does the following:
- Creates a new array double the size of the original one.
- Copies all elements of the old array to the new array, preserving the order.
Adjust the algorithm so that the insertion of new element will be in constant time in the worst case.
The limitation here is we must use arrays as stack implementation.
The worst case is when for example the old stack of size $n$ is full and now we need to insert a new element. So we create a new stack $S_2$ of size $2n$ and we want to insert the new element to $S_2[n+1]$.
I'm stuck with the constant time requirement, I'd appreciate any hints to the right direction.
NB: I'm aware that the title is a bit general, I couldn't think of anything more specific, if you know under which category of algorithms it falls under please let me know and I'll edit the heading.