# Why the Library Check Slows Down and Play Doesn't: O(1) and O(n)

Tell a job whose work stays the same as the library grows from one whose work grows with it, and read their growth rates aloud: O(1), constant time, and O(n), linear time.

Novice · Software Development · Updated November 17, 2026

By Gregor Dzierzon

## After this lesson you can

- Read O(1) and O(n) aloud and say what each one means
- Tell O(1) code from O(n) code: one lookup by position versus a loop over every item

## Key takeaways

- O(1), read "big O of one", is constant time: the work stays the same however much data there is.
- O(n), read "big O of n", is linear time: the work grows in step with the data, so twice the data is twice the work.
- Reading one item by its position is O(1). Looking at every item, one after another, is O(n).
- Reading from the other end, or splitting the reading between two helpers, makes O(n) work faster but leaves it O(n), because it still doubles when the data doubles.

Your music app has a new feature: before it downloads a song, it checks "is this song already in my library?", so nobody pays twice. On your phone, with 40 songs, the check is over before you notice. Then the app's biggest users arrive, collectors with 40,000 songs, and the check slows down for them. "Play track 214", on the same phones, is as quick as ever. Two jobs in the same app: one stayed the same as the library grew, and one grew with it. Developers name both, and these two names are the ones you'll write most often, and the first two you'll be asked about in any class or interview on Big-O.

## What would you try?

The check reads the library's titles from the top and stops when it finds the song. Most songs in the store *aren't* in your library, so most checks read every title before answering "no": 40 reads for you, 40,000 for a collector.

**Read from the bottom instead.** The newest songs are at the bottom, so a song you added yesterday is found in a read or two. But a song you don't have is still "no" only after every title: 40,000 reads.

**Split the reading between two helpers.** A phone has more than one processor core, so two of them each read half: 20,000 reads each, finished in about half the time. Better. But when the collector's library doubles to 80,000, each helper reads 40,000, and the check is as slow as it was before the split.

**Buy a faster phone.** The same 40,000 reads, each a little quicker. Then the library doubles, and the reads double with it.

| What we tried | Reads for a song you don't have, at 40,000 songs | At 80,000 songs |
|---|---|---|
| Read from the top | 40,000 | 80,000 |
| Read from the bottom | 40,000 | 80,000 |
| Two helpers, half each | 20,000 each | 40,000 each |

Every try made the check faster, and none of them stopped it from growing.

## The questions that lead to it

**When the library doubled, which job doubled?** The check: it reads every title, so twice the titles is twice the reading, whichever end it starts from and however many helpers share it.

**Which job stayed the same?** "Play track 214". The app goes straight to position 214, as in *Why "Play Track 750,000" Is Instant and "Find Golden Hour" Isn't: Memory as Mailboxes*: one step, with 40 songs or 40 million.

So the useful question isn't "how many seconds?" It's "what happens to the work when the library doubles?" That answer has a name, for each kind of job.

## Both in code

The code makes libraries of 1,000, 2,000 and 4,000 songs (`Song 0`, `Song 1` and so on), plays track 214 of each, and checks each one for *Golden Hour*, which none of them has, counting the titles it reads:

```csharp
List<string> MakeLibrary(int songCount)
{
    List<string> library = new List<string>();
    for (int number = 0; number < songCount; number++)
    {
        library.Add("Song " + number);
    }
    return library;
}

int ReadsToCheck(List<string> library, string title)
{
    int reads = 0;
    foreach (string song in library)
    {
        reads++;
        if (song == title)
        {
            break;
        }
    }
    return reads;
}

foreach (int songCount in new int[] { 1000, 2000, 4000 })
{
    List<string> library = MakeLibrary(songCount);
    Console.WriteLine("Songs: " + songCount + ", play track 214 (" + library[214] + "): 1 step, check for Golden Hour: " + ReadsToCheck(library, "Golden Hour") + " reads");
}
```

```text
Songs: 1000, play track 214 (Song 214): 1 step, check for Golden Hour: 1000 reads
Songs: 2000, play track 214 (Song 214): 1 step, check for Golden Hour: 2000 reads
Songs: 4000, play track 214 (Song 214): 1 step, check for Golden Hour: 4000 reads
```

```java
List<String> makeLibrary(int songCount) {
    List<String> library = new ArrayList<>();
    for (int number = 0; number < songCount; number++) {
        library.add("Song " + number);
    }
    return library;
}

int readsToCheck(List<String> library, String title) {
    int reads = 0;
    for (String song : library) {
        reads++;
        if (song.equals(title)) {
            break;
        }
    }
    return reads;
}

void main() {
    for (int songCount : new int[] { 1000, 2000, 4000 }) {
        List<String> library = makeLibrary(songCount);
        IO.println("Songs: " + songCount + ", play track 214 (" + library.get(214) + "): 1 step, check for Golden Hour: " + readsToCheck(library, "Golden Hour") + " reads");
    }
}
```

```text
Songs: 1000, play track 214 (Song 214): 1 step, check for Golden Hour: 1000 reads
Songs: 2000, play track 214 (Song 214): 1 step, check for Golden Hour: 2000 reads
Songs: 4000, play track 214 (Song 214): 1 step, check for Golden Hour: 4000 reads
```

```python
def make_library(song_count):
    library = []
    for number in range(song_count):
        library.append(f"Song {number}")
    return library


def reads_to_check(library, title):
    reads = 0
    for song in library:
        reads += 1
        if song == title:
            break
    return reads


for song_count in [1000, 2000, 4000]:
    library = make_library(song_count)
    print(f"Songs: {song_count}, play track 214 ({library[214]}): 1 step, check for Golden Hour: {reads_to_check(library, 'Golden Hour')} reads")
```

```text
Songs: 1000, play track 214 (Song 214): 1 step, check for Golden Hour: 1000 reads
Songs: 2000, play track 214 (Song 214): 1 step, check for Golden Hour: 2000 reads
Songs: 4000, play track 214 (Song 214): 1 step, check for Golden Hour: 4000 reads
```

```javascript
function makeLibrary(songCount) {
  const library = [];
  for (let number = 0; number < songCount; number++) {
    library.push("Song " + number);
  }
  return library;
}

function readsToCheck(library, title) {
  let reads = 0;
  for (const song of library) {
    reads++;
    if (song === title) {
      break;
    }
  }
  return reads;
}

for (const songCount of [1000, 2000, 4000]) {
  const library = makeLibrary(songCount);
  console.log(`Songs: ${songCount}, play track 214 (${library[214]}): 1 step, check for Golden Hour: ${readsToCheck(library, "Golden Hour")} reads`);
}
```

```text
Songs: 1000, play track 214 (Song 214): 1 step, check for Golden Hour: 1000 reads
Songs: 2000, play track 214 (Song 214): 1 step, check for Golden Hour: 2000 reads
Songs: 4000, play track 214 (Song 214): 1 step, check for Golden Hour: 4000 reads
```

```typescript
function makeLibrary(songCount: number): string[] {
  const library: string[] = [];
  for (let number = 0; number < songCount; number++) {
    library.push("Song " + number);
  }
  return library;
}

function readsToCheck(library: string[], title: string): number {
  let reads = 0;
  for (const song of library) {
    reads++;
    if (song === title) {
      break;
    }
  }
  return reads;
}

for (const songCount of [1000, 2000, 4000]) {
  const library = makeLibrary(songCount);
  console.log(`Songs: ${songCount}, play track 214 (${library[214]}): 1 step, check for Golden Hour: ${readsToCheck(library, "Golden Hour")} reads`);
}
```

```text
Songs: 1000, play track 214 (Song 214): 1 step, check for Golden Hour: 1000 reads
Songs: 2000, play track 214 (Song 214): 1 step, check for Golden Hour: 2000 reads
Songs: 4000, play track 214 (Song 214): 1 step, check for Golden Hour: 4000 reads
```

Playing track 214 is a single step at every size. The check reads every title, so its reads double each time the library does.

**Try it.** Add 8000 to the list of library sizes and run it again. Then change `"Golden Hour"` to `"Song 0"`: now every check stops on its first read, because the song it wants is at the top. (*Fast in the Demo, Slow for Users: Best, Worst and Average* is about exactly that difference.)

## How it got its name

These two answers to "what happens when the data doubles?" were so useful that they got names.

Work that stays the same however much data there is is called **constant time**. In Big-O it's written **O(1)**, and read aloud as "big O of one". The 1 doesn't mean exactly one step. It means "a fixed amount of work that doesn't grow": one step, or three, but never more because there's more data. Playing track 214 is O(1).

Work that grows in step with the data is called **linear time**, written **O(n)** and read "big O of n". Remember from *How Slow Will It Get? Counting Steps* that n is the amount of data, so O(n) says "the work grows the same way n does". It's called linear because, drawn on a chart, it's a straight line. The library check is O(n), and so is every try in the table above: reading from the bottom, splitting it in two or buying a faster phone changes how quick each read is, not how the reading grows.

You've met both away from screens. At a festival gate, "who has wristband #214?" is one look at the list by number, however many people came. "Is Ana Ruiz on the guest list?" means reading names from the top, and a list twice as long can take twice the reading.

![Two side-by-side scenes at a music festival gate: on the left, a staff member looking straight at line 214 of a numbered wristband list, labeled "Constant time, O(1): one look, however many wristbands"; on the right, a staff member reading a long guest list name by name from the top with a finger partway down, labeled "Linear time, O(n): twice the names, twice the reading"](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/494383ad1b3b4d4e80ff67e56cab8e6b.webp)

## How to tell them apart

When you read code, two questions sort these out:

- **Does it go straight to one item,** by its position or its number? Then the work doesn't depend on n: **O(1)**.
- **Does it walk through the items,** one after another, maybe to the end? Then the work grows with n: **O(n)**.

A loop over a list is the sign of O(n). Its absence, with one direct lookup, is the sign of O(1).

Can the library check itself become O(1)? Yes: Module 5's hash tables answer "do I have this one?" without reading the list. For now, being able to spot which kind of job you're looking at is the whole skill.

## Check yourself

2 questions to try on the lesson page.

## So what

Many data structures in this course exist to turn a slow O(n) search into a fast O(1) lookup. When you can spot which one a piece of code does, you can tell whether it will keep up as the data grows, before your biggest users tell you.

## Key terms

- [Big-O Notation](https://www.ask-codey.com/glossary/big-o-notation)
- [Constant Time](https://www.ask-codey.com/glossary/constant-time)
- [Linear Time](https://www.ask-codey.com/glossary/linear-time)

## Cheat sheets

- [Why the Library Check Slows Down and Play Doesn't: O(1) and O(n)](https://www.ask-codey.com/cheat-sheets/big-o-constant-and-linear-cheat-sheet)

Source: https://www.ask-codey.com/lessons/big-o-constant-and-linear
