Java · Course navigation

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.

On this page

Before you start

Java arrays and classes.

Show that doubling a backing array makes append cost O(1) on average even though some appends copy everything.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

Code example

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

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

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

Behind the scenes

How Java processes this code

The Java compiler produces bytecode. The JVM loads the class and invokes its main method.

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.