I am not going to bore you with the mathematical representations and their relevance in algorithm analysis. Amortized time a.k.a amortized run time is the concept that helps us understand how ArrayList, backed by an Array, stay with in O(1) run time for insertion while inifinitely (say that with in the confines of HW limitation) growing to accommodate new elements as you wish to insert and shrink as you delete.

“gradually write off the initial cost” is the definition of Amorization as found in the Dictionary. Amortization in computer science is doing additional work in-frequently for performance gain. A parallel can be drawn between dictonary definition and Computer Science definition as to writing of the additional work done infrequently which becomes negligible in the light of performance gain in the long run.

ArrayList , as mentioned before  is backed by an Array. But wait, isnt array fixed size and the shouldn’t array size be defined while initlaily while creating an array? Yes, you are on the right track. This is where the amortization comes to rescue.

Lets say we create an array, double the size of the initial array, which is filled up to three quarters of its capacity and copy the elements into the newly created array. One might be thiking isnt copying into a new array addional work that needs to be performed? Yes, but here the amazing part that works in favor. This doubling and copying happens so infrequently that for the rest the time the work on array is done in constant time i.e. O(1). Hold on, when do we exacly do this creation and copying? The best practice is to perform creation and copying when the original array is atleast three quarters full (mathematical explanation below).  So, we agree that creating a brand new array double the size of initial array and copying elements helps to maintain performance along with the flexibility to grow infinitely. Logical question that follows this thought process is, what do we do when we start deleting elements ? Isnt memory wasted because the array holds on to the memory but does not contain data ? Yes ,  you were right all along. I like the way you think. You truly think like an engineer. Here is what we are going to do to address that.

On deleting the elements from the ArrayList, we create a new array with reduced size and copy the elements into the new array. But when exactly do we do that ? or in other words when do we create a shrunken array and copy the elements into new array ? The best practice to do that is exactly the opposite of what we did while increasing the size. we create a new array half the size of the original array when the number of elements in the original array if atmost one quarter the size of the original array.  This will keep the memory wastage in check. Ok, enough with the theory, how does this all work out mathematically? Here goes that too…