Course contentsShow
← Java
Lesson 1017 of 2,87024. List ImplementationsFree lesson

Counting Operations: N Adds and Log N Resizes

Why doubling/multiplying capacity means only logarithmic resizes for N elements.

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.