Amortization

Amortization #

Content Note

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!

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:

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