# Is Adding a Song Slow? Amortized Cost

One add to a growing playlist just copied 1,024 songs. Work out what adding really costs over a long run of adds, why doubling beats growing a little at a time, and what "amortized O(1)" promises.

Journeyman · Data Structures · Updated November 17, 2026

By Gregor Dzierzon

## After this lesson you can

- Explain why adding to the end of a growing array is O(1) on average, even though a move is O(n)
- Add up the copies a growing array makes as it grows, by doubling or by one slot at a time

## Key takeaways

- A growing array that doubles only moves when its count reaches 1, 2, 4, 8, 16 and so on, so moving days get rarer as it grows.
- Adding n items copies fewer than 2n items in all, so each add costs O(1) on average: amortized O(1).
- Growing by one slot at a time instead copies about n²/2 items in all: the handshakes again.
- Amortized means an average over a long run of operations, which is a promise, not luck.
- When one slow add is a problem, as in a game drawing a frame, set the capacity up front instead.

**Before this:** *The Ninth Song Won't Fit: Growing Arrays*. Doubling made room for any number of songs, at the price of a moving day now and then.

A teammate is reviewing your growing playlist, and they've found something. Adding song 1,025 took a thousand times longer than adding song 1,024: the array was full, so that one add made an array of 2,048 slots and copied 1,024 songs across. "So `add` is O(n)," they write. "And a playlist of a million songs calls it a million times. Isn't that O(n²)?"

It's a fair question, and the documentation for your language's list seems to dodge it: "adding to the end is amortized O(1)". This lesson settles it, with numbers, and by the end you'll know exactly what that footnote promises.

## What would you try?

**Go by the worst case.** The slowest add copies every song so far, so call every add O(n). Then a million adds cost up to about a million times half a million copies: half a trillion. That's the teammate's answer. It treats every add as a moving day, though, and most adds aren't.

**Count every copy.** Start with a capacity of 1 and add songs one at a time. The array is full, and moves, when the count reaches 1, then 2, then 4, then 8. Each moving day copies the songs it has, and the next one waits twice as long.

| Adding song number | Moving day? | Songs copied |
|---|---|---|
| 1 | no | 0 |
| 2 | yes, 1 to 2 slots | 1 |
| 3 | yes, 2 to 4 slots | 2 |
| 4 | no | 0 |
| 5 | yes, 4 to 8 slots | 4 |
| 6, 7, 8 | no | 0 |
| 9 | yes, 8 to 16 slots | 8 |

For 9 songs, that's 1 + 2 + 4 + 8 = 15 copies.

![A bar chart of the cost of adding each of 16 songs: most bars are 1 step tall, the cost of writing the song, with taller bars at songs 2, 3, 5 and 9 for the moving days (2, 3, 5 and 9 steps). A dashed line shows the average cost per song staying below 3](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/03dd56753d9b4ae28a32e477291571d3.webp)

Counting by hand stops being fun quickly, so here's a program that counts. `copiesWhenDoubling` doubles the capacity on every moving day, like the playlist in the last lesson. `copiesWhenGrowingByOne` rents just one more slot each time, for comparison.

```csharp
long CopiesWhenDoubling(long songs)
{
    long capacity = 1, count = 0, copies = 0;
    for (long i = 0; i < songs; i++)
    {
        if (count == capacity)
        {
            copies += count;
            capacity *= 2;
        }
        count++;
    }
    return copies;
}

long CopiesWhenGrowingByOne(long songs)
{
    long capacity = 1, count = 0, copies = 0;
    for (long i = 0; i < songs; i++)
    {
        if (count == capacity)
        {
            copies += count;
            capacity += 1;
        }
        count++;
    }
    return copies;
}

foreach (long songs in new long[] { 1000, 1000000 })
{
    Console.WriteLine(songs + " songs, doubling: " + CopiesWhenDoubling(songs) + " copies");
    Console.WriteLine(songs + " songs, one more slot: " + CopiesWhenGrowingByOne(songs) + " copies");
}
```

```text
1000 songs, doubling: 1023 copies
1000 songs, one more slot: 499500 copies
1000000 songs, doubling: 1048575 copies
1000000 songs, one more slot: 499999500000 copies
```

```java
long copiesWhenDoubling(long songs) {
    long capacity = 1, count = 0, copies = 0;
    for (long i = 0; i < songs; i++) {
        if (count == capacity) {
            copies += count;
            capacity *= 2;
        }
        count++;
    }
    return copies;
}

long copiesWhenGrowingByOne(long songs) {
    long capacity = 1, count = 0, copies = 0;
    for (long i = 0; i < songs; i++) {
        if (count == capacity) {
            copies += count;
            capacity += 1;
        }
        count++;
    }
    return copies;
}

void main() {
    for (long songs : new long[] {1000, 1000000}) {
        IO.println(songs + " songs, doubling: " + copiesWhenDoubling(songs) + " copies");
        IO.println(songs + " songs, one more slot: " + copiesWhenGrowingByOne(songs) + " copies");
    }
}
```

```text
1000 songs, doubling: 1023 copies
1000 songs, one more slot: 499500 copies
1000000 songs, doubling: 1048575 copies
1000000 songs, one more slot: 499999500000 copies
```

```python
def copies_when_doubling(songs):
    capacity, count, copies = 1, 0, 0
    for i in range(songs):
        if count == capacity:
            copies += count
            capacity *= 2
        count += 1
    return copies


def copies_when_growing_by_one(songs):
    capacity, count, copies = 1, 0, 0
    for i in range(songs):
        if count == capacity:
            copies += count
            capacity += 1
        count += 1
    return copies


for songs in [1000, 1000000]:
    print(f"{songs} songs, doubling: {copies_when_doubling(songs)} copies")
    print(f"{songs} songs, one more slot: {copies_when_growing_by_one(songs)} copies")
```

```text
1000 songs, doubling: 1023 copies
1000 songs, one more slot: 499500 copies
1000000 songs, doubling: 1048575 copies
1000000 songs, one more slot: 499999500000 copies
```

```javascript
function copiesWhenDoubling(songs) {
  let capacity = 1, count = 0, copies = 0;
  for (let i = 0; i < songs; i++) {
    if (count === capacity) {
      copies += count;
      capacity *= 2;
    }
    count++;
  }
  return copies;
}

function copiesWhenGrowingByOne(songs) {
  let capacity = 1, count = 0, copies = 0;
  for (let i = 0; i < songs; i++) {
    if (count === capacity) {
      copies += count;
      capacity += 1;
    }
    count++;
  }
  return copies;
}

for (const songs of [1000, 1000000]) {
  console.log(`${songs} songs, doubling: ${copiesWhenDoubling(songs)} copies`);
  console.log(`${songs} songs, one more slot: ${copiesWhenGrowingByOne(songs)} copies`);
}
```

```text
1000 songs, doubling: 1023 copies
1000 songs, one more slot: 499500 copies
1000000 songs, doubling: 1048575 copies
1000000 songs, one more slot: 499999500000 copies
```

```typescript
function copiesWhenDoubling(songs: number): number {
  let capacity = 1, count = 0, copies = 0;
  for (let i = 0; i < songs; i++) {
    if (count === capacity) {
      copies += count;
      capacity *= 2;
    }
    count++;
  }
  return copies;
}

function copiesWhenGrowingByOne(songs: number): number {
  let capacity = 1, count = 0, copies = 0;
  for (let i = 0; i < songs; i++) {
    if (count === capacity) {
      copies += count;
      capacity += 1;
    }
    count++;
  }
  return copies;
}

for (const songs of [1000, 1000000]) {
  console.log(`${songs} songs, doubling: ${copiesWhenDoubling(songs)} copies`);
  console.log(`${songs} songs, one more slot: ${copiesWhenGrowingByOne(songs)} copies`);
}
```

```text
1000 songs, doubling: 1023 copies
1000 songs, one more slot: 499500 copies
1000000 songs, doubling: 1048575 copies
1000000 songs, one more slot: 499999500000 copies
```

C# and Java count with `long`, a whole number with room up to about 9 quintillion, because 499,999,500,000 is too big for an `int`, which stops at about 2.1 billion. Python's `int` never runs out of room, and JavaScript's numbers hold whole numbers exactly up to about 9 quadrillion.

| How it grows | 1,000 songs | 1,000,000 songs | Copies per song |
|---|---|---|---|
| Doubling | 1,023 copies | 1,048,575 copies | always under 2 |
| One more slot | 499,500 copies | 499,999,500,000 copies | about half the playlist |

## The questions that lead to it

**Which adds are expensive?** Only the moving days, and with doubling they come at songs 2, 3, 5, 9, 17, 33: further and further apart.

**How big is each moving day, next to the ones before it?** Add them up: 1 + 2 + 4 + 8 = 15, and the next move copies 16. Each moving day copies about as much as **all the moving days before it put together**, plus one. So the total never catches up with twice the number of songs.

**So what does one add cost, spread over all of them?** Fewer than 2 copies, plus the one write for the song itself: fewer than 3 steps on average, for 9 songs or a million. The teammate's half a trillion was the worst single add, multiplied by every add. The real total is about a million.

## How it got its name

Think of a gym that charges $120 once a year. You could say "the gym costs $120 on one day and nothing on the others", which is true but not much help for planning. Or you could say "it costs about $10 a month", which is how most people budget it. Spreading a rare big cost over all the days it covers is called **amortizing** it, from an old word for paying off a debt bit by bit.

A growing array's moving day is the $120. The cost of an add averaged over a long run of adds is its **amortized cost**, and for a doubling array it's constant: **amortized O(1)**, read "amortized big O of one". A single add can be O(n) on moving day; the average over all the adds is O(1).

**One more slot each time** has no such luck. 1,000 songs cost 499,500 copies, and you've seen that number before: it's the handshakes at a party of 1,000 guests from *Why the Duplicates Button Crawls: O(n²)*. Every add is a moving day, so the total is O(n²), and each add costs O(n) even on average. That gap, about a million copies against half a trillion, is why every language's list grows by multiplying its capacity (by 2, or by about 1.5, which works the same way), never by adding a fixed number of slots.

## A promise, not luck

"On average" here doesn't mean "usually, if you're lucky", like the average case in *Fast in the Demo, Slow for Users: Best, Worst and Average*. It's a guarantee about any long run of adds: n adds in a row never cost more than about 3n steps, whatever the songs are. One add might be slow, but the run as a whole never is.

If one slow add would be a real problem (a game that must draw a frame every few milliseconds), the honest fix is to set the capacity up front, which the next lesson shows, so moving day never comes during play.

**Try it.** Change the doubling (`capacity *= 2`) to tripling, and run it again. Are there more copies or fewer? Then try growing by 100 slots at a time: is it still O(n²)?

## Check yourself

2 questions to try on the lesson page.

## So what

Now when documentation says an operation is "amortized O(1)", you know the deal: rare expensive moments, paid for by many cheap ones, with a promise about the total. You can answer the teammate too: one add can be O(n), and a million of them are still about a million steps. You'll meet the same idea again in hash tables, which double too when they fill up.

## Key terms

- [Amortized Cost](https://www.ask-codey.com/glossary/amortized-cost)
- [Dynamic Array](https://www.ask-codey.com/glossary/dynamic-array)
- [Constant Time](https://www.ask-codey.com/glossary/constant-time)

## Cheat sheets

- [Is Adding a Song Slow? Amortized Cost](https://www.ask-codey.com/cheat-sheets/ds-amortized-cost-cheat-sheet)

Source: https://www.ask-codey.com/lessons/ds-amortized-cost
