Amortized complexity in Java

Problem

The import that copies everything

The shop imports the orders from an old system one by one. Someone wrote the import so that with every order the array gets one place bigger:

static long importOrders(int n) {
    int[] orders = new int[0];
    long copies = 0;
    for (int i = 0; i < n; i++) {
        copies += orders.length;
        orders = Arrays.copyOf(orders, orders.length + 1);
        orders[orders.length - 1] = 100000 + i;
    }
    return copies;
}

It looks harmless: one line per order. But every new array is a copy of the old one plus one place. The program counts the copies:

for (int n : new int[] {1000, 10000}) {
    System.out.println(n + " orders: " + importOrders(n) + " copies");
}

1000 orders: 499500 copies
10000 orders: 49995000 copies

With 10 times more orders there are 100 times more copies. With 100 000 orders there are 4 999 950 000, and the import, which takes a blink in the test, now runs for minutes. Yet ArrayList.add on the same 100 000 orders finishes at once, although it too sometimes copies the whole array. How?

The idea

The list does not grow by one place

Inside, a list is an array with more places than elements. When it fills up, it makes a new, bigger array and copies everything into it:

ArrayList<String> cart = new ArrayList<>(3);
cart.add("Bread");
cart.add("Milk");
cart.add("Coffee");
cart.add("Butter");
cart.remove("Milk");
System.out.println(cart);
System.out.println("Items: " + cart.size());

Step by step, in words

cart points to an ArrayList object. Inside there is an array with 3 places and a size counter.
add puts each element in the first free place and increases size.
The array is full. ArrayList makes a new one with 4 places and copies the three elements into it.
The object now points to the new array, and nobody needs the old one. "Butter" goes into the free place.
remove removes "Milk", and everything after it moves one place to the left. No hole is left.
From the outside you see only a list of three items: ArrayList does the copying and the shifting.

The secret is how much bigger the new array is. If it has one more place, every addition after the full array copies everything, like the import above. If it is twice as big, the next copy comes only after as many additions again.

See it

Your own array that doubles

Here is the same mechanism written by hand, with a counter of the copies. The array starts with one place:

class OrderList {
    private int[] items = new int[1];
    private int size = 0;
    long copies = 0;

    void add(int order) {
        if (size == items.length) {
            int[] bigger = new int[items.length * 2];
            for (int i = 0; i < size; i++) {
                bigger[i] = items[i];
                copies++;
            }
            items = bigger;
        }
        items[size] = order;
        size++;
    }
}

for (int n : new int[] {9, 1000}) {
    OrderList orders = new OrderList();
    for (int i = 0; i < n; i++) {
        orders.add(100000 + i);
    }
    System.out.println(n + " orders: " + orders.copies + " copies" + ", 2n = " + 2 * n);
}

9 orders: 15 copies, 2n = 18
1000 orders: 1023 copies, 2n = 2000

class OrderList {
    private int[] items = new int[1];
    private int size = 0;
    long copies = 0;

    void add(int order) {
        if (size == items.length) {
            int[] bigger = new int[items.length * 2];
            for (int i = 0; i < size; i++) {
                bigger[i] = items[i];
                copies++;
            }
            items = bigger;
        }
        items[size] = order;
        size++;
    }
}

OrderList orders = new OrderList();
for (int i = 0; i < 9; i++) {
    orders.add(100000 + i);
}

Step by step, in words

The array starts with one place, and size is 0. We count only the copies of old elements.
The first order: there is room, add writes it. Copies: 0.
The second: the array is full. A new array with 2 places, and the old order is copied into it: 1 copy.
The third: full again, 4 places and 2 copies. The fourth goes in without copying.
The fifth copies 4, the ninth 8. The copies grow, but between them come more and more additions without copying.
9 additions, 1 + 2 + 4 + 8 = 15 copies, under 2n = 18. Spread over all additions, that is under 2 per addition: O(1) amortized.

An addition that finds the array full copies everything: 1, 2, 4, 8, 16 … But after it come as many additions without copying as it copied. The sum 1 + 2 + 4 + … + 2ᵏ is always under 2 · 2ᵏ, and the last copy 2ᵏ is under n. So the copies are under 2n, however big n is.

The idea

Amortized complexity

One addition can cost O(n): the one that copies everything. But n additions cost under 3n operations in total: n writes and under 2n copies. Divided by n, that is under 3 per addition: O(1).

The cost spread over a whole sequence of operations is called amortized complexity. Adding at the end of a list is O(1) amortized.

This is not "on average for a random input". The promise holds for every sequence of additions, with no luck: the expensive ones are rare, and always that rare.

Try it

Predict the output

Five orders in an array that starts with one place and doubles. How many copies?

class OrderList {
    private int[] items = new int[1];
    private int size = 0;
    long copies = 0;

    void add(int order) {
        if (size == items.length) {
            int[] bigger = new int[items.length * 2];
            for (int i = 0; i < size; i++) {
                bigger[i] = items[i];
                copies++;
            }
            items = bigger;
        }
        items[size] = order;
        size++;
    }
}

for (int n : new int[] {5}) {
    OrderList orders = new OrderList();
    for (int i = 0; i < n; i++) {
        orders.add(100000 + i);
    }
    System.out.println(n + " orders: " + orders.copies + " copies");
}

Answer

5 orders: 7 copies

5 orders: 4 copies

5 orders: 10 copies

See it

One place more: O(n²)

The same class, except that the new array has one more place:

int[] bigger = new int[items.length + 1];

for (int n : new int[] {9, 1000}) {
    OrderList orders = new OrderList();
    for (int i = 0; i < n; i++) {
        orders.add(100000 + i);
    }
    System.out.println(n + " orders: " + orders.copies + " copies");
}

9 orders: 36 copies
1000 orders: 499500 copies

With 1000 orders doubling copies 1023 times, and growing by one place 499 500 times: 1 + 2 + … + 999. Run both growths and look at the curves. We count only the copies:

Growth ×2: copies O(n)
Growth +1: copies O(n²)

Algorithm	n = 10	n = 1,000	n = 100,000
Growth ×2: copies	15	1,023	131,071
Growth +1: copies	45	499,500	≈ 4,995,000,000

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

Doubling grows like a straight line: O(n) in total, O(1) per addition. Growing by one place grows like a parabola: O(n²) in total, O(n) per addition.

Try it

Fill in

How many places does the new array have, so that adding is O(1) amortized?

if (size == items.length) {
    int[] bigger = new int[];

Try it

Find the bug

A colleague replaced the doubling "so it does not waste memory". With 1000 orders the test passes quickly, and the nightly import of 100 000 drags on:

for (int n : new int[] {1000, 100000}) {
    OrderList orders = new OrderList();
    for (int i = 0; i < n; i++) {
        orders.add(100000 + i);
    }
    System.out.println(n + " orders: " + orders.copies + " copies");
}

1000 orders: 4510 copies
100000 orders: 49951000 copies

With 100 times more orders there are 10 000 times more copies. Which line is the bug on?

Pick the line with the bug.

The idea

How each language grows

No language doubles exactly, but every one multiplies:

Java ArrayList: the new size is the old one plus half, ×1.5. An empty list gets 10 places at the first addition.
C# List<T>: ×2;
Python (CPython): about ×1.125;
JavaScript (V8): about ×1.5.

Any factor above 1 gives O(1) amortized. The smaller it is, the more copies (under 3n for ×1.5, under 9n for ×1.125) and the fewer empty places after a growth. The choice is a trade between time and memory, as in the lesson "Space complexity".

More precisely, if you are curious

O(1) amortized does not mean every addition is fast. The addition that copies is O(n). In most programs you do not notice it, but in a program that must not stop (a till, a game, audio processing), one addition of the millionth element may be the slow one. If you know how many elements there will be, set the places up front: new ArrayList<>(n). Then the list never copies.

ArrayList also has ensureCapacity(n) for a list that already exists.

The bound for ×2 has another form too: every addition "pays" 2 copies in advance and saves them. When the array with k elements fills up, the last k/2 additions have saved k, exactly what the copy costs. The savings never go negative, so the sum is under 2n.

Exercise

Growth as in Java

Solve the task in your editor.

Growth by half. Change the growth of OrderList so that the new array has the old places plus half (at least one place more). Count the copies for 1000 and for 100 000 orders. Are they under 2n? And under 3n?

1000 orders: 2137 copies, 2n = 2000
100000 orders: 276521 copies, 2n = 200000

More tasks

Removing from the end. Add removeLast. When should the array shrink, so that removing is O(1) amortized too? Try "by half, when it is half full" and alternate adding and removing exactly at the boundary. Then try "by half, when it is a quarter full". Why is the second O(1) amortized and the first not?
How many places it wastes. After 1000 additions with doubling, how many places are empty? And with growth ×1.5?

Test

Check yourself

1. An array doubles when it fills up. How many copies do 1000 additions make in total if it starts with 1 place?1000 × 1000Exactly 1000Under 2000

2. What does "adding is O(1) amortized" mean?Every addition is fastAdding is fast on average for a random inputn additions cost O(n) in total, although one of them copies everything

3. A colleague changes the growth from ×2 to +1000 places "so it does not waste memory". What happens with a million additions?It gets faster, because the array is smallerNothing, 1000 is a lot of placesThe copies become about n²/2000: half a billion instead of about a million

4. Why does Java grow by ×1.5 and not ×2 or ×10?The bigger the factor, the fewer the copies, but the more empty places after a growthOnly ×1.5 gives O(1) amortizedBecause ×1.5 is faster for the processor

5. A program for the till must not stop for more than a millisecond per addition. What do you do?You set the places up front if you know how many elements there will beYou switch to growth +1Nothing, adding is O(1)

Amortized complexity

Cookies