# Answer It in One Step: Trading Memory for Time

Answer "how long are the first few songs?" in one step instead of a loop, by spending a little memory on running totals, and measure both sides of that trade in Big-O: time complexity and space complexity.

Apprentice · Software Development · Updated November 17, 2026

By Gregor Dzierzon

## After this lesson you can

- Explain space complexity as how the extra memory grows as the data grows
- Describe a trade-off where spending memory saves time, such as keeping running totals
- Choose whether to spend memory to save time, from how often a question is asked and how much memory there is

## Key takeaways

- Space complexity is how the extra memory a piece of code needs grows as its data grows. It's written in Big-O too.
- Spending memory can save time. Running totals take n extra numbers, and then answer each question in one step instead of up to n.
- The trade-off pays when the same kind of question is asked many times. For one question, it isn't worth building.
- Adding up each time costs up to 1,000,000 steps a day for 1,000 questions on 1,000 songs; running totals cost 2,000 steps and 1,000 numbers of memory.

**Before this:** *Is It Really Slow? Measure Your Own Code* (time and step counts tell you how slow; this lesson is about making a slow question fast).

Before a road trip, the music app shows "the first 5 songs: 17 minutes 10 seconds", so you know how far down the playlist to load. Users ask it about different numbers of songs all day: the first 5, the first 12, the first 300. On a 1,000-song playlist, about 1,000 times a day. Each answer is quick on its own. But the app's server answers every one of them, and the work piles up.

## What would you try?

**Add up the lengths each time.** For "the first k songs", add up k song lengths. That's up to 1,000 steps a question, O(n), and in the worst case, when every question asks about the whole playlist, 1,000 × 1,000 = **1,000,000 steps a day**. No extra memory at all.

**Remember the last answer.** If the next question asks about the same number of songs, answer from memory. But users ask about different numbers all day, so the last answer is rarely the one needed. Most questions still add up from scratch.

**Remember every answer as it's asked.** Better: each number of songs is added up only once. But the first time each one is asked, it's still up to 1,000 steps, and with a thousand different questions that's nearly the same work.

| What we tried | Steps per question | Steps a day, worst case | Extra memory |
|---|---|---|---|
| Add up each time | up to 1,000 | up to 1,000,000 | none |
| Remember the last answer | up to 1,000, unless the same question repeats | nearly 1,000,000 | 1 number |
| Remember each answer when first asked | up to 1,000 the first time | still up to about 1,000,000 | up to 1,000 numbers |

## The questions that lead to it

**What does the app do most?** Answer questions, a thousand times a day. The playlist changes rarely.

**What if every possible answer were already written down,** before anyone asked? There are only 1,000 of them: the first 1 song, the first 2, and so on up to all 1,000.

**And can they all be worked out at once?** Yes: walk through the playlist once, keeping a running sum. After song 1, write down the sum; after song 2, write it down again. One walk, 1,000 steps, and every answer is written down. The total of the first k songs is sitting at position k − 1, and any question takes **one step**.

The code below answers three questions both ways (the first 8, 5 and 3 songs) on an 8-song playlist, counting the steps each way takes:

```csharp
int[] lengths = { 210, 185, 240, 200, 195, 230, 180, 220 };
int[] questions = { 8, 5, 3 };

int stepsAddingUp = 0;
int answer = 0;
foreach (int k in questions)
{
    answer = 0;
    for (int song = 0; song < k; song++)
    {
        answer += lengths[song];
        stepsAddingUp++;
    }
}

int[] runningTotals = new int[lengths.Length];
int stepsWithTotals = 0;
int sum = 0;
for (int song = 0; song < lengths.Length; song++)
{
    sum += lengths[song];
    runningTotals[song] = sum;
    stepsWithTotals++;
}
foreach (int k in questions)
{
    answer = runningTotals[k - 1];
    stepsWithTotals++;
}

Console.WriteLine("First 5 songs: " + runningTotals[4] + " seconds");
Console.WriteLine("Steps adding up each time: " + stepsAddingUp);
Console.WriteLine("Steps with running totals: " + stepsWithTotals);
Console.WriteLine("Extra memory for running totals: " + runningTotals.Length + " numbers");
```

```text
First 5 songs: 1030 seconds
Steps adding up each time: 16
Steps with running totals: 11
Extra memory for running totals: 8 numbers
```

```java
void main() {
    int[] lengths = {210, 185, 240, 200, 195, 230, 180, 220};
    int[] questions = {8, 5, 3};

    int stepsAddingUp = 0;
    int answer = 0;
    for (int k : questions) {
        answer = 0;
        for (int song = 0; song < k; song++) {
            answer += lengths[song];
            stepsAddingUp++;
        }
    }

    int[] runningTotals = new int[lengths.length];
    int stepsWithTotals = 0;
    int sum = 0;
    for (int song = 0; song < lengths.length; song++) {
        sum += lengths[song];
        runningTotals[song] = sum;
        stepsWithTotals++;
    }
    for (int k : questions) {
        answer = runningTotals[k - 1];
        stepsWithTotals++;
    }

    IO.println("First 5 songs: " + runningTotals[4] + " seconds");
    IO.println("Steps adding up each time: " + stepsAddingUp);
    IO.println("Steps with running totals: " + stepsWithTotals);
    IO.println("Extra memory for running totals: " + runningTotals.length + " numbers");
}
```

```text
First 5 songs: 1030 seconds
Steps adding up each time: 16
Steps with running totals: 11
Extra memory for running totals: 8 numbers
```

```python
lengths = [210, 185, 240, 200, 195, 230, 180, 220]
questions = [8, 5, 3]

steps_adding_up = 0
answer = 0
for k in questions:
    answer = 0
    for song in range(k):
        answer += lengths[song]
        steps_adding_up += 1

running_totals = [0] * len(lengths)
steps_with_totals = 0
total = 0
for song in range(len(lengths)):
    total += lengths[song]
    running_totals[song] = total
    steps_with_totals += 1
for k in questions:
    answer = running_totals[k - 1]
    steps_with_totals += 1

print(f"First 5 songs: {running_totals[4]} seconds")
print(f"Steps adding up each time: {steps_adding_up}")
print(f"Steps with running totals: {steps_with_totals}")
print(f"Extra memory for running totals: {len(running_totals)} numbers")
```

```text
First 5 songs: 1030 seconds
Steps adding up each time: 16
Steps with running totals: 11
Extra memory for running totals: 8 numbers
```

```javascript
const lengths = [210, 185, 240, 200, 195, 230, 180, 220];
const questions = [8, 5, 3];

let stepsAddingUp = 0;
let answer = 0;
for (const k of questions) {
  answer = 0;
  for (let song = 0; song < k; song++) {
    answer += lengths[song];
    stepsAddingUp++;
  }
}

const runningTotals = new Array(lengths.length);
let stepsWithTotals = 0;
let sum = 0;
for (let song = 0; song < lengths.length; song++) {
  sum += lengths[song];
  runningTotals[song] = sum;
  stepsWithTotals++;
}
for (const k of questions) {
  answer = runningTotals[k - 1];
  stepsWithTotals++;
}

console.log(`First 5 songs: ${runningTotals[4]} seconds`);
console.log(`Steps adding up each time: ${stepsAddingUp}`);
console.log(`Steps with running totals: ${stepsWithTotals}`);
console.log(`Extra memory for running totals: ${runningTotals.length} numbers`);
```

```text
First 5 songs: 1030 seconds
Steps adding up each time: 16
Steps with running totals: 11
Extra memory for running totals: 8 numbers
```

```typescript
const lengths: number[] = [210, 185, 240, 200, 195, 230, 180, 220];
const questions: number[] = [8, 5, 3];

let stepsAddingUp = 0;
let answer = 0;
for (const k of questions) {
  answer = 0;
  for (let song = 0; song < k; song++) {
    answer += lengths[song];
    stepsAddingUp++;
  }
}

const runningTotals: number[] = new Array(lengths.length);
let stepsWithTotals = 0;
let sum = 0;
for (let song = 0; song < lengths.length; song++) {
  sum += lengths[song];
  runningTotals[song] = sum;
  stepsWithTotals++;
}
for (const k of questions) {
  answer = runningTotals[k - 1];
  stepsWithTotals++;
}

console.log(`First 5 songs: ${runningTotals[4]} seconds`);
console.log(`Steps adding up each time: ${stepsAddingUp}`);
console.log(`Steps with running totals: ${stepsWithTotals}`);
console.log(`Extra memory for running totals: ${runningTotals.length} numbers`);
```

```text
First 5 songs: 1030 seconds
Steps adding up each time: 16
Steps with running totals: 11
Extra memory for running totals: 8 numbers
```

Adding up each time took 8 + 5 + 3 = 16 steps and no extra memory. The running totals took 8 steps to build, then 1 step per question: 11 in all, and 8 extra numbers of memory.

![Two rows of eight boxes: the top row holds the song lengths 210, 185, 240, 200, 195, 230, 180 and 220 seconds; the bottom row holds the running totals 210, 395, 635, 835, 1030, 1260, 1440 and 1660, with box 4, 1030, highlighted as the answer for the first 5 songs, read in one step](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/ac6903b7c9a941498fcb6b4d345162b9.webp)

## How it got its name

Writing answers down ahead of time is an idea so useful that Big-O measures it from both sides.

So far, Big-O has described **time**: how the steps grow as the data grows (*time complexity*). It describes memory the same way. **Space complexity** is how the *extra* memory a piece of code needs grows as its data grows. The data itself doesn't count, only what the code adds:

- A search that keeps one counter, however long the playlist: **O(1)** extra memory.
- Code that makes one extra number for every song, like the running totals: **O(n)** extra memory.

You already know the trade from school. A student writes the important page numbers of a textbook on sticky notes along the cover. The notes take a little room, and writing them took a few minutes, but every time a homework question asks about "the chapter on cells", the student flips straight there instead of paging from the start.

![A spiral notebook with colored sticky notes along its edge, each labeled with a topic, and a hand flipping straight to the page under one note; beside it, the same notebook without notes, with a hand paging from the front](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/63a27d27f2f8457a92d2a52360aa7aa0.webp)

## When the trade pays

Back to the real app: 1,000 questions a day on a 1,000-song playlist, counting the worst case, where every question asks about the whole playlist:

| | Adding up each time | Running totals |
|---|---|---|
| Steps per question | up to 1,000: **O(n)** | 1: **O(1)** |
| Steps for 1,000 questions | up to 1,000,000 | 1,000 to build + 1,000 to answer = 2,000 |
| Extra memory | none: **O(1)** | 1,000 numbers: **O(n)** |

That's the trade-off from *800 Lost Items and a Line at the Desk: What a Data Structure Is*, with Big-O on both sides: **O(n) extra memory buys O(1) questions**. It pays when the same kind of question comes up again and again. For a single question it doesn't: building the totals costs as much as answering it once the slow way. And it costs something when the playlist changes: a song added near the top means writing the totals after it again.

**Try it.** Add a fourth question, the first 7 songs, and predict both step counts before you run it. Then make the playlist twice as long (copy the eight lengths again): which count grows faster?

## Check yourself

2 questions to try on the lesson page.

## So what

When code is too slow, one of the first questions to ask is "could I spend some memory to save this work?" And when memory is tight, on a phone or a small device, the reverse: "can I afford the memory this speed costs?" Now you can answer both in Big-O.

## Key terms

- [Space Complexity](https://www.ask-codey.com/glossary/space-complexity)
- [Trade-Off](https://www.ask-codey.com/glossary/trade-off)
- [Time Complexity](https://www.ask-codey.com/glossary/time-complexity)

## Cheat sheets

- [Answer It in One Step: Trading Memory for Time](https://www.ask-codey.com/cheat-sheets/big-o-time-vs-memory-cheat-sheet)

Source: https://www.ask-codey.com/lessons/big-o-time-vs-memory
