# Amortization

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

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

**!!**