# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cs61b.bencuan.me/asymptotics/amortization.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.