[Learning note] Amortized analysis case: Dynamic array insertion complexity

Amortized analysis is sometimes used in algorithm analysis when average time complexity is more concerned than individual operations. I stumble upon this today when I am reviewing hash map implementation and find it fun.

Case 1: Dynamic array insertion

Consider a dynamic array of size N. When insertion is performed, if the dynamic array still has vacant locations, insertion will take O(1) time. But if the dynamic array is full (all almost full depends on the implementation), we will reallocate an array of size 2N and move original elements to this new array along with the newly added element. This single operation will cost about O(2N) time. (2N time to allocate the new array, at least constant time to delete the original array, N time to move the element, constant time to add the newly inserted element). So we will have a timeline similar to:

When amortized, resizing cost is distributed to all N insertions, leaving an average complexity of nearly O(1).

Case 2: Hash table resizing

With dynamic array insertion in mind, hash table resizing is quite similar. Consider a size N hashmap containing M elements. Its load factor is \( \frac{N}{M} \). The resizing scheme is as follow: If the load balance exceeds 1, we will double hash table size. If load balance is less than \( \frac{1}{4} \), hash table size is halve.

Use the same analyzing scheme, the amortized cost for insertion is calculated as: (Figure redrawn from here.)

When amortized, the average cost is still O(1).

As to shrinking hash table, we start with \( N = \frac{M}{2} \) since this is what remains after one last shrinking operation. We need to perform at least \( \frac{M}{4} \) deletion operations before another shrinking is needed. This shrinking will have time cost of O( \( \frac{M}{2}\) ). Distribute this time to all \( \frac{M}{4} \) deletion operations. The amortized time complexity is still O(1).