Aside — Amortized Time Complexity

Warning

This explanation of amortized time complexity analysis is brief and high-level as it is outside the scope of this course. It is only included here for those interested as some may find that the additional context helps with their understanding.

  • There’s actually a bit of a gotcha in the push example for an ArrayStack

 1    @Override
 2    public boolean push(T element) {
 3        if (size() == stack.length) {
 4            stack = expandCapacity(stack);
 5        }
 6        stack[top] = element;
 7        top++;
 8        return true;
 9    }
10
11    /**
12     * Returns a new array with double the size of the stack array container and copy the contents from the old array to
13     * the new array.
14     */
15    @SuppressWarnings("unchecked")
16    private T[] expandCapacity(T[] oldStack) {
17        T[] newStack = (T[]) new Object[oldStack.length * 2];
18        for (int i = 0; i < oldStack.length; i++) {
19            newStack[i] = oldStack[i];
20        }
21        return newStack;
22    }

  • Since expandCapacity is an \(O(n)\) method

  • And since push calls expandCapacity, push will at least be \(O(n)\)

  • However, how often is expandCapacity actually called?

Amortization

  • The trick is to realize that the work can be amortized, or, spread out over multiple calls of push

  1. Consider an empty ArrayStack with a capacity of \(n\)

  2. A total of \(n\) constant time push operations can occur before the capacity it hit

    • \(n \times O(1)\) operations

  3. The \((n+1)^{th}\) push will require a call to expandCapacity, which is a linear time operation

    • \(1 \times O(n)\) operation

  • In other words, the \(O(n)\) operation gets called once every \(n\) constant time calls of push

  • This \(O(n)\) work can be amortized/spread out over the \(n\) constant time calls

  • Consider all this as a roughly calculated expression to shows how much work is being done, on average, over the \(n + 1\) push calls

    \(=\frac{n \times O(1) + 1 \times O(n)}{n + 1}\)

    \(= \frac{n \times O(1)}{n + 1} + \frac{1 \times O(n)}{n + 1}\)

    \(\approx O(1) + O(1)\)

    \(\approx 2 \times O(1)\)

    \(\approx O(1)\)

  • The below figures show a visualization of how one can think of the work being amortized

../../_images/amortization0.png

Depiction of the amount of work taking place for each of the \(n + 1\) calls to push.

../../_images/amortization1.png

A depiction of all the work required for the \(n + 1\) calls to push amortized over the previous \(n\) calls to push.