Java: amortized cost of a growing array
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.
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);
}
}