Amortized Analysis

What is it? Why it is important?

5 min readOct 3, 2020

Amortized analysis

A method for analyzing a given algorithm’s complexity, or how much of a resource, especially time or memory, it takes to execute. The motivation for amortized analysis is that looking at the worst-case run time per operation, rather than per algorithm, can be too pessimistic.

While certain operations for a given algorithm may have a significant cost in resources, other operations may not be as costly. The amortized analysis considers both the costly and less costly operations together over the whole series of operations of the algorithm. This may include accounting for different types of input, length of the input, and other factors that affect its performance.

Dynamic Array

Let’s take a look at a dynamic array, the array that grows in size as more elements that are added to it, like ArrayList in Java or std::vector in C++.

If we started out with a dynamic array of size 4, we could push 4 elements onto it, and each operation would take constant time. Yet pushing a fifth element onto that array would take longer as the array would have to create a new array of double the current size 8, copy the old elements onto the new array, and then add the new element. The next three push operations would similarly take constant time, and then the subsequent addition would require another slow doubling of the array size.

If we use simple analysis, the worst-case cost of insertion is O(n). Therefore, the worst-case cost of n inserts is n * O(n) which is O(n²). This analysis gives an upper bound, but not a tight upper bound for n insertions as all insertions don’t take Θ(n) time. We always heard that push to an array is O(1), then how it is actually being calculated. Let’s take a look at several other cases.

Opening a Donut shop

Franchise cost $1,000,000
Cost per donut $1

How much the cost of opening a Donut shop? The first one costs $1,000,001 and the rest cost $1. If we want to make a profit of $1 per donut, we can sell the first donut for $1,000,002 and each donut after that for $2.

The problem is how do we sell the first donut. No one gonna buys a donut cost a million and 2 dollars. However, by our cost analysis, we saw that the first one did cost $1,000,001 to make.

What we can do is scatter the costs to a million donuts. Assume we gonna sell 1 million donuts and we scatter the cost of the franchise over the 1 million donuts, then the cost per donut will be $2. If we want to make a profile of $1 per donut, we can sell each donut for $3.

Binary Counter

If there are k=4 bits needed to represent a number. What is the cost (number of bits flipped) of increment a number? What would be the cost of increment number numbers?

If a bit gets flip from 0 to 1, the cost will be increment. From 0000 to 0001 because only 1 zero will be flip to 1. From 0011 to 0100 , you need 3 flip for the second, third, and fourth bit, as 0 to 1, 1 to 0, and 1 to 0.

By looking at the cost of the image, we can see sometimes the cost can be 1, sometimes it can be 2, be 3, or 4. Depends on the number, the cost is different. If we consider the amount of number is n and the length of the bits is k then we can consider the worst-case complexity is O(n k).

However, let’s try to scatter the cost like what we did at the donut shop. First, we can try to determine, since every time we increment an even number, we just turn the least significant bit from 0 to 1. 0010 to 0011 , we just change the most right side bit from 0 to 1. For an odd number, we can also see the pattern where we will change all lower-order 1’s to 0 until we get the first 0, we change that to a 1. 0011 to 0100 , we change the 1 we keep getting to 0, then when we hit 0 we change it to 1 then done.

We can see the cost is not random, but there is a pattern here. But how do we able to amortize the cost like the donut shop? Let’s take another example of transit.

Transit from Tokyo to Osaka

The cost is $10 to go from Tokyo to Osaka
The cost is $10 to come back to Tokyo from Osaka
Total cost is $20

We can buy the ticket when we are in Tokyo, pay $10 for a trip to Osaka. Then buy the ticket on Osaka for the trip back to Tokyo for another $10. The total cost will be $20.

However, we can think it this way, what if we bought the round trip ticket for $20? It would be $20 to go up to Osaka and a free ride to go back (because we pre-paid the ride home), the total cost is still $20.

With that logic let’s see what we can do on the binary counter.

Isn’t it true that every bit that starts from 0 that goes to 1, at some point will go back to 0? 0000 to 0001 to 0010 , you can see the least significant bit that changes to 1 will come back to 0. With that logic, we might as well just buy the returning ticket back to 0. Every time a 0 becomes a 1, we pay twice the amount of the cost. We can see the cost of 0000 to 0001 become 2, because we pay upfront. But the good news is when 1 goes back to 0, we don’t need another cost. The same thing when 0011 to 0100 , since we already pay the cost for the 1 to become a 0, we only need the cost for 0 to 1 which is also a round trip of 2.

Then we can see it not O(n k) but it is O(2 n), removing the constant we get O(n).

Implement the logic to the dynamic array, we can see how spreading the cost of doubling the size of the array actually not making the complexity of the push element is O(n²) but O(n) since O(n²) only for the worst case, but logically thinking of spreading the amortized cost for doubling but most of the time it just insert to the existing location, it costs O(1).