# Amortization

Last updated

Last updated

Please read Asymptotic Analysis Basics first. If you don't, none of this will make any sense!

**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:

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

Finally, we can add in the new element!

**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!**

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:

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)$ **!!**