Java: amortized cost of a growing array

Show that doubling a backing array makes append cost O(1) on average even though some appends copy everything.

Java

class Main {
  static class IntList {
    private int[] data = new int[1];
    private int size = 0;
    long copies = 0;

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

  public static void main(String[] args) {
    IntList list = new IntList();
    for (int i = 1; i <= 16; i++) {
      list.add(i);
    }
    System.out.println("appends=16 copies=" + list.copies);
    System.out.println("copies per append=" + (double) list.copies / 16);
  }
}

Output

appends=16 copies=15
copies per append=0.9375

Explanation

Amortized analysis averages the cost of a sequence of operations. A dynamic array such as ArrayList stores its items in a plain array. When it is full, the next append allocates an array twice as large and copies every existing item.

That one append is expensive, but it happens rarely. With doubling, the copies over n appends are 1 + 2 + 4 + ... which is less than 2n, so the average cost per append is constant. The program counts the copies for 16 appends.

Explore the dry run

Guided walkthroughReady

1class Main {

2 static class IntList {

3 private int[] data = new int[1];

4 private int size = 0;

5 long copies = 0;

7 void add(int value) {

8 if (size == data.length) {

9 int[] bigger = new int[data.length * 2];

10 for (int i = 0; i < size; i++) {

11 bigger[i] = data[i];

12 copies++;

13 }

14 data = bigger;

15 }

16 data[size++] = value;

17 }

18 }

20 public static void main(String[] args) {

21 IntList list = new IntList();

22 for (int i = 1; i <= 16; i++) {

23 list.add(i);

24 }

25 System.out.println("appends=16 copies=" + list.copies);

26 System.out.println("copies per append=" + (double) list.copies / 16);

27 }

28}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
When the array is full, allocate twice the capacity. This happens at sizes 1, 2, 4, and 8.	`capacity 1 → 2 → 4 → 8 → 16`	—
Each existing item is copied once per growth: 1 + 2 + 4 + 8 copies in total.	`copies = 15`	—
15 copies were needed for 16 appends.	`copies = 15`	appends=16 copies=15
The average is under one copy per append.	`copies = 15`	appends=16 copies=15 copies per append=0.9375

Cost and common mistakes

Each append is amortized O(1); n appends cost O(n) total time and O(n) space.

Growing by a fixed amount, such as 10 slots at a time, makes n appends cost Θ(n²) overall. The growth must be geometric.
Amortized O(1) does not mean every append is fast: a single append can still take O(n).

Try it yourself

How many copies are needed for 32 appends?

Reveal answer and reasoning

31 copies (1 + 2 + 4 + 8 + 16), which is again less than the number of appends.

Java: amortized cost of a growing array

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading