Amortized Analysis | Engineering Interview Kit

Concept

Imagine you are saving money in a jar. Every day you put in $1. That operation takes $O(1)$ time.
But once every 100 days, the jar gets full. You have to go to the bank, wait in line for an hour, deposit the coins, and buy a new jar. That operation takes $O(N)$ time.

If an interviewer asks: “What is the time complexity of putting money in the jar?”

Technically, the absolute Worst Case is $O(N)$ (the bank day).
But saying the action is $O(N)$ feels wrong, because 99% of the time, it is instant $O(1)$ .

Amortized Analysis is the mathematical concept of “spreading out” the cost of a rare, expensive operation over all the cheap operations that led up to it.
When we spread the 1 hour bank trip across the 100 fast days, the average time per day is still effectively instant. Therefore, we say the operation is Amortized $O(1)$ .

Dynamic Arrays (The Classic Example)

In computer science, the most famous example of Amortized Analysis is the Dynamic Array (e.g., [] in JavaScript/Python, ArrayList in Java).

When you create an array in memory, the CPU allocates a strict, fixed physical space (e.g., 4 slots).

const arr = [10, 20, 30, 40];

If you push 50 to the array, it doesn’t fit. The CPU has to perform a massive operation:

Find a brand new space in memory that is twice as large (8 slots).
Physically copy the 4 old items to the new space (takes $O(N)$ time).
Insert the new item.

The Complexity of .push():

Best/Average Case: There is empty space. It is instant $O(1)$ .
Worst Case: The array is full. It must copy $N$ elements. It is $O(N)$ .
Amortized Case: Because the array doubles in size every time it resizes, the expensive $O(N)$ operation happens increasingly rarely (after 4 items, then 8, then 16, then 32…). If you push 1,000 items, you only trigger 10 resizes. Averaged out over all 1,000 pushes, the cost mathematically converges to exactly $O(1)$ .

Therefore, when an interviewer asks for the time complexity of pushing to an array, the correct answer is: “It is Amortized $O(1)$ .”

Interview Questions

Q: A junior developer looks at a Dynamic Array and says: “Pushing an element is worst-case $O(N)$ . Unshifting (inserting at the front) an element is also worst-case $O(N)$ . Therefore, they are both exactly the same performance.” Why are they completely wrong?
A: They are ignoring Amortized time.

Pushing to the back only triggers an $O(N)$ resize occasionally. Over time, it averages out to Amortized $O(1)$ . It is incredibly fast.
Unshifting to the front forces the CPU to physically shift every single existing element one slot to the right every single time you call it, regardless of array capacity. Over time, it remains a strict $O(N)$ operation. Unshifting is mathematically thousands of times slower than Pushing in a dynamic array.