Amortized complexity analysis — [Notes]

7 min readJun 17, 2022

--

∘ Explain amortized complexity to a 5 year old and a 25 year old computer science graduate
∘ When is amortized complexity used/helpful in an technical interview?
· Time Analysis
· Amortized Time Analysis
· Amortized time
· Amortized analysis
· 🎯 Aggregate Method (brute force sum)
∘ Dynamic Array — Aggregate method
· 🎯 Banker’s Method (tokens)
∘ Dynamic Array — Banker’s method
· 🎯 Physicist’s Method (potential function, Φ)
∘ Dynamic Array — Physicist’s Method
· Alternative to Doubling the Array Size
∘ Cannot use constant amount
· References

Explain amortized complexity to a 5 year old and a 25 year old computer science graduate

To a 5-year-old:

Imagine you have a big bag of candy and you want to eat it all. You can either eat all of it at once or eat a few pieces every day until it’s gone. If you eat all of it at once, it might take a long time and you might get a tummy ache. But if you eat a few pieces every day, it will be easier and won’t hurt your tummy.

Now, imagine the bag of candy is like a big computer program. Sometimes the program needs to do a lot of work at once, but other times it can do a little bit of work every time it runs. Just like eating candy, doing a little bit of work every time is easier and won’t hurt the program.

To a 25-year-old:

Amortized complexity is a way of analyzing the performance of algorithms or data structures that have occasional high-cost operations. It takes into account not only the worst-case scenario but also the average cost over a series of operations.

For example, let’s say we have a dynamic array that starts with a certain capacity and doubles in size every time it reaches its capacity. If we add n elements to the array, the worst-case scenario is that we have to resize the array log n times, which has a high cost. However, if we look at the cost over all n insertions, we see that most of them are cheap and only a few are expensive. The amortized cost per operation is therefore much lower than the worst-case cost.

By considering the amortized complexity, we can get a better idea of the overall performance of an algorithm or data structure and make informed decisions about when to use them.

When is amortized complexity used/helpful in an technical interview?

Amortized complexity can be used in technical interviews in a few different ways. Here are some examples:

Analyzing the time complexity of an algorithm: If you are asked to analyze the time complexity of an algorithm that has occasional high-cost operations, such as a dynamic array, you can use the concept of amortized complexity to give a more accurate estimate of the average cost per operation.
Comparing the performance of data structures: If you are asked to compare the performance of different data structures, such as a linked list and an array, you can use the concept of amortized complexity to show how certain operations have a different cost depending on the data structure used.
Designing an algorithm or data structure: If you are asked to design an algorithm or data structure, you can use the concept of amortized complexity to optimize the performance by reducing the number of high-cost operations and spreading out the cost over multiple operations.

Overall, being familiar with the concept of amortized complexity can demonstrate to the interviewer that you have a deep understanding of algorithmic analysis and can think critically about the performance of code.

Time Analysis

Provides time complexity for worst case ( n ~ infinity)
Dynamic array — to push elements 1 to n → O(n*n)
→ copy whole array n elements * n times

Amortized Time Analysis

Do we need worst case analysis all the time?
Way of analysing time/memory/resource consumed per operation or an optimised run.
Dynamic array — O(n)
→ The insertion takes O(n) when the capacity has been reached, and the amortized time for each insertion is O(1).[source]
→ The insertion takes O(2X) when the capacity of X has been reached, and the amortized time for each insertion is O(1). [source]

Amortized time

Amortized time is the way to express the time complexity when an algorithm has the very bad time complexity only once in a while besides the time complexity that happens most of time
average time taken per operation, if you do many operations.
Example — dynamic array

Amortized analysis

🎯 Nothing changes in the code : runtime analysis only

Amortized analysis is used for algorithms that have expensive operations that happen only rarely.

🎯 Done for a Sequence of operations
Normally when we analyze algorithm, we look into worst case of individual operations
Sometime, looking at worst case may be too severe. We may want to know total worst case for sequence of operations
This analysis is used when the occasional operation is very slow, but most of the operations which are executing very frequently are faster. In Data structures we need amortized analysis for Hash Tables, Disjoint Sets etc.
Ways to to do amortized analysis —
1. Aggregate method — brute force sum
2. Banker’s method — tokens
3. Physicist’s method — potential function Φ

🎯 Aggregate Method (brute force sum)

The aggregate method is used to find the total cost. If we want to add a bunch of data
then we need to find the amortized cost by this formula.
For a sequence of n operations, the cost is −

Amortized complexity analysis is most commonly used with data structures that have state that persists between operations.
The basic idea is that an expensive operation can alter the state so that the worst case cannot occur again for a long time, thus amortizing its cost.

Let T1, T2, …, Tk be the complexities of a sequence of operations on a data structure. The amortized complexity of a single operation in this sequence is (T1 + T2 + …+ Tk) / k.

Amortized complexity is the total time per operation, evaluated over a sequence of multiple operations.
The idea is to guarantee the total time of the entire sequence, while allowing single operations to be much slower then the amortized time.
E.g. in our case a single call might take O(log⁡n) in the worst case, but if we do m such calls back to back we will end up with an average time of O(α(n)).

Dynamic Array — Aggregate method

We only resize every so often
Many O(1) operations are followed by O(N) operation
What is total cost of inserting many elements?

🎯 Banker’s Method (tokens)

Charge extra for each operation
save the extra charge as tokens in your data structure (conceptually).
Use the tokens to pay for expensive operations.
Like an amortizing loan

Dynamic Array — Banker’s method

🎯 Physicist’s Method (potential function, Φ)

Define a potential function , Φ, which maps states of the data structure to integers :
→ Φ( h0) = 0
→ Φ(ht) ≥ 0
amortized cost of operation t: cₜ + Φ(hₜ) — Φ(hₜ₋₁)
choose Φ so that:
→ cₜ is small, then potential increases
→ cₜ is large, then potential decreases by the same scale.