Counting Operations: N Adds and Log N Resizes
You'll learn why adding N elements to an ArrayList triggers surprisingly few resizes—only logarithmic in N.
The Mathematical Reality
When you add N elements to an initially empty ArrayList, you perform exactly N add operations. But how many costly resize operations happen?
Because the capacity grows by multiplying (1.5× in Java's implementation), the number of resizes is logarithmic—specifically log₁.₅(N), which grows very slowly.
Why Logarithmic?
Think of it this way: starting from capacity 10, each resize multiplies the capacity:
- Resize 1: capacity becomes 15
- Resize 2: capacity becomes 22
- Resize 3: capacity becomes 33
- Resize 4: capacity becomes 49
- ...and so on
To reach capacity N, you need approximately log₁.₅(N) resizes. For 1,000 elements, that's only about 17 resizes. For 1,000,000 elements? Only about 35 resizes!
The Big Picture
N operations (the adds) + log N operations (the resizes that each copy O(n) elements) = O(N) total work
This is the foundation of amortized O(1) performance. You spread the cost of a few expensive resizes across many cheap adds. The resize count grows so slowly—logarithmically—that even though each individual resize is expensive, they don't dominate the total cost.
Key Takeaway: Adding N elements triggers only log N resizes because exponential growth (multiplying capacity) means you double/multiply your way to large capacities extremely quickly—the mathematical inverse relationship between exponential growth and logarithmic counting.