# Amortization

{% hint style="warning" %}
Please read [Asymptotic Analysis Basics](https://cs61b.bencuan.me/asymptotics/asymptotics) first. If you don't, none of this will make any sense!
{% endhint %}

**Amortization** means **spreading out.**

Sometimes, an operation takes different amounts of time for different values of $$n$$. Rather than having to report runtimes for each different case, we can instead average all of them out and report the **amortized runtime.**

This is especially good for functions where most actions have a low cost, but a few have a high cost. We'll see an example of this further down the page!

## A Case Study: Resizing Arrays

As you probably know, normal Java arrays don't resize. If we create a `new int[5]` then that array will always have a length of 5.

But what if we wanted to make an array resize itself every time it reaches capacity? (Like a `List`!) Let's see what happens when we **add one to the array size:**

First, we have to make a new array with a new size:

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M6wXcIVYe5N0yofLWWm%2F-M6waZGqM4s2ys3FjMv-%2Fimage.png?alt=media\&token=b67dc294-9598-4d61-8e13-02f0866ea2f2)

Then, we have to copy over all of the old elements over:

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M6wXcIVYe5N0yofLWWm%2F-M6wb9S62_IdwHvQCP3D%2Fimage.png?alt=media\&token=26afad1a-fbef-4667-a646-6170f24bdda8)

Finally, we can add in the new element!

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M6wXcIVYe5N0yofLWWm%2F-M6wbEgyPVlaVWjokt8A%2Fimage.png?alt=media\&token=6b6b7948-a859-4ac9-a9bf-e212475e0f82)

**Let's analyze the runtime of this operation.**

* A single resizing will take $$\Theta(n)$$ time**.**
* Adding a single element will take $$\Theta(1)$$ time**.**
* Together, a single operation will take $$\Theta(n+1)$$ time, which simplifies into  $$\Theta(n)$$ .
* Since we're doing a n-operation n times, **the end result is a resizing function that is**$$\Theta(n^2)$$. **We can do better with the power of amortization!**

### **What if we doubled the size instead of adding one?**

* A single resizing will take $$\Theta(2n)$$ time \_\*\*\_which simplifies into $$\Theta(n)$$ time.
  * We do this every time the array hits a power of 2 (2, 4, 8, 16, 32 ...). 
* Adding a single element will take $$\Theta(1)$$ time.
  * We do this every time we add a new element, so in all we add n elements. Therefore, this is an 
    * $$\Theta(n)$$operation.

**Therefore, the unsimplified function is:** $$\Theta(n + (2 + 4 + 8 ... +2^i))$$ where $$2^i$$ is the largest power of two less than n. This might not seem clear on its own, so let's rewrite it:

$$
\theta(n + (\frac{n}{2} + \frac{n}{4} + ... + 8 + 4 + 2))
$$

Intuitively, this looks like this:

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M7-sXxWjkAxaF6Fyr1f%2F-M7-t3I--rmRiAMVBP6u%2Fimage.png?alt=media\&token=dc699a2a-10ed-40d6-a240-282a85567a30)

Mathematically, it looks like this:

$$
n + n\sum\_{n=1}^{n}(\frac{1}{2})^n
$$

Which simplifies to $$2n$$if you recall your power series properties . **Therefore, this approach is** $$\Theta(n)$$ **!!**

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-MO0PHDrgLWmUYQtMWXO%2F-MO0PcUJFt9TqNa5Vv1P%2Fimage.png?alt=media\&token=e0464b23-ca1a-4663-98f4-704c51a0563e)