Once a Push() call is invoked on a full stack (stack.size = stack.capacity), we increase the capacity of a stack (or a queue, or a hash-table) using IncreaseCapacity(): 1. Allocate a new array with 2 stack.capacity cells; 2. Copy all items from the original array to the new array, delete the old array. Analogously to this, once stack.size is small in comparison to stack.capacity, we can decrease the capacity and clear some memory using DecreaseCapacity():

1. Allocate a new array with stack.capacity/2 cells;

2. Copy all items from the original array to the new array, delete the old array.

Note that both IncreaseCapacity() and DecreaseCapacity() run in ?(n)-time.

Prove that invoking DecreaseCapacity() whenever stack.size = stack.capacity/3 maintains constant amortized cost. That is, show that any sequence of n Push()/Pop() instructions has amortized cost of O(1). You may assume stack.capacity = 1 initially.

I've already seen this answered on chegg, but the formatting is terrible and I couldn't understand how they got the answer. Please be very clear!! (I don't need any pseudocode)