# Sorting a Million Songs, and the Playlist You Can't Compute: O(n log n) and O(2ⁿ)

See why a good sort handles a million songs in under a second while the obvious ways take most of a day, and why a playlist that fills exactly 60 minutes can't be found by trying every combination: O(n log n) and O(2ⁿ).

Apprentice · Software Development · Updated November 17, 2026

By Gregor Dzierzon

## After this lesson you can

- Place O(n log n) between O(n) and O(n²), and name sorting as where you'll meet it
- Explain why O(2ⁿ) work becomes impossible even for a small amount of data

## Key takeaways

- O(n log n), read "big O of n log n", is a little more than O(n) and far less than O(n²). Good sorting runs at this speed.
- O(2ⁿ), read "big O of two to the n", is exponential time: adding one item doubles the work.
- Exponential work is fine for 10 items, slow for 30, and impossible for 100, whatever the computer.
- Picking the smallest title again and again is about 500 billion comparisons for a million songs; a good sort is about 20 million: n × the 20 halvings of a million.

**Before this:** *Why the Duplicates Button Crawls: O(n²)* (comparing every pair grows four times when the songs double).

Two more complaints about the music app, and two more growth rates. The first: a user imports a million songs, and the A to Z view has to put them in order before it can show anything. The second: a user asks for a road-trip playlist that fills **exactly** 60 minutes. One of these has a fast answer that's hard to see. The other has no fast answer at all, and knowing that early saves you weeks.

## Sorting a million songs: what would you try?

**Pick the smallest title, again and again.** Read all million titles to find the first in A to Z order, then read the 999,999 left to find the next, and so on. That's about 500 billion comparisons. In Python on a laptop, sorting 10,000 songs this way takes about 6 seconds, and a million songs is 100 times as many, so 10,000 times the work: most of a day.

**Slot each song into place.** Take the songs one at a time and slide each into its spot in a growing sorted list. A song can be compared with every song already placed, so the worst case is the same 500 billion. Same growth.

Both tries compare every song with almost every other: the O(n²) shape from the duplicates button. And yet your language's built-in sort puts the same million songs in order in under a second (0.7 seconds in Python, measured on the same laptop). It makes roughly 20 million comparisons. The code below works out both numbers, for a thousand songs and for a million:

```csharp
foreach (long songs in new long[] { 1000, 1000000 })
{
    long pickTheSmallest = songs * (songs - 1) / 2;
    long halvings = 0;
    for (long left = songs; left > 1; left = (left + 1) / 2)
    {
        halvings++;
    }
    Console.WriteLine("Songs: " + songs + ", pick the smallest each time: " + pickTheSmallest + " comparisons, a good sort: about " + (songs * halvings));
}
```

```text
Songs: 1000, pick the smallest each time: 499500 comparisons, a good sort: about 10000
Songs: 1000000, pick the smallest each time: 499999500000 comparisons, a good sort: about 20000000
```

```java
void main() {
    for (long songs : new long[] { 1000, 1000000 }) {
        long pickTheSmallest = songs * (songs - 1) / 2;
        long halvings = 0;
        for (long left = songs; left > 1; left = (left + 1) / 2) {
            halvings++;
        }
        IO.println("Songs: " + songs + ", pick the smallest each time: " + pickTheSmallest + " comparisons, a good sort: about " + (songs * halvings));
    }
}
```

```text
Songs: 1000, pick the smallest each time: 499500 comparisons, a good sort: about 10000
Songs: 1000000, pick the smallest each time: 499999500000 comparisons, a good sort: about 20000000
```

```python
for songs in [1000, 1000000]:
    pick_the_smallest = songs * (songs - 1) // 2
    halvings = 0
    left = songs
    while left > 1:
        left = (left + 1) // 2
        halvings += 1
    print(f"Songs: {songs}, pick the smallest each time: {pick_the_smallest} comparisons, a good sort: about {songs * halvings}")
```

```text
Songs: 1000, pick the smallest each time: 499500 comparisons, a good sort: about 10000
Songs: 1000000, pick the smallest each time: 499999500000 comparisons, a good sort: about 20000000
```

```javascript
for (const songs of [1000, 1000000]) {
  const pickTheSmallest = (songs * (songs - 1)) / 2;
  let halvings = 0;
  for (let left = songs; left > 1; left = Math.floor((left + 1) / 2)) {
    halvings++;
  }
  console.log(`Songs: ${songs}, pick the smallest each time: ${pickTheSmallest} comparisons, a good sort: about ${songs * halvings}`);
}
```

```text
Songs: 1000, pick the smallest each time: 499500 comparisons, a good sort: about 10000
Songs: 1000000, pick the smallest each time: 499999500000 comparisons, a good sort: about 20000000
```

```typescript
for (const songs of [1000, 1000000]) {
  const pickTheSmallest = (songs * (songs - 1)) / 2;
  let halvings = 0;
  for (let left = songs; left > 1; left = Math.floor((left + 1) / 2)) {
    halvings++;
  }
  console.log(`Songs: ${songs}, pick the smallest each time: ${pickTheSmallest} comparisons, a good sort: about ${songs * halvings}`);
}
```

```text
Songs: 1000, pick the smallest each time: 499500 comparisons, a good sort: about 10000
Songs: 1000000, pick the smallest each time: 499999500000 comparisons, a good sort: about 20000000
```

C# and Java use `long` because 499,999,500,000 is too big for an `int`.

## The question that leads to it

**20 million is 1,000,000 × 20. Where have you seen 20 next to a million before?** In *How Many Times Can You Halve a Million? O(log n)*: a million can be halved 20 times before one is left.

So a good sort does about **n × log n** comparisons: every song takes part in about 20 rounds of work, instead of being compared with every other song. *How* a sort manages that is one of the best ideas in this course, and Module 4 builds it step by step. For now, the count is enough.

## How it got its name: O(n log n)

This growth rate is written **O(n log n)**, read "big O of n log n", and called **linearithmic time** (linear times logarithmic). It's the speed of every good sorting method, including the one built into your language. See where it sits among the others:

| Songs to sort | n (read each once) | n log n (a good sort) | n² (compare every pair) |
|---|---|---|---|
| 1,000 | 1,000 | about 10,000 | 1,000,000 |
| 1,000,000 | 1,000,000 | about 20,000,000 | 1,000,000,000,000 |

O(n log n) is a little more work than reading every item once, and enormously less than comparing every pair. That gap is why sorting a list first, then doing something clever with it, so often beats a nested loop.

## The 60-minute playlist: what would you try?

Now the road trip. You have your favorite songs, each a few minutes long, and you want a playlist that adds up to exactly 60 minutes.

**Try every combination.** Each song is either in the playlist or out of it. Check every possible playlist, add up its minutes, and keep one that hits 60 exactly. Count how many playlists that is: with 1 song there are 2 (with it, or empty). Add a song, and every playlist you had can now be made with the new song or without it, so the count **doubles**.

![A branching diagram for three songs: the first song splits into in or out, each of those splits again for the second song, and again for the third, ending in eight possible playlists](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/6dd965edd67349c1b8917458943c9640.webp)

This code doubles a count once for every song, the same way:

```csharp
foreach (int songs in new int[] { 10, 20, 30, 40 })
{
    long playlists = 1;
    for (int song = 0; song < songs; song++)
    {
        playlists = playlists * 2;
    }
    Console.WriteLine("Songs: " + songs + ", possible playlists: " + playlists);
}
```

```text
Songs: 10, possible playlists: 1024
Songs: 20, possible playlists: 1048576
Songs: 30, possible playlists: 1073741824
Songs: 40, possible playlists: 1099511627776
```

```java
void main() {
    for (int songs : new int[] {10, 20, 30, 40}) {
        long playlists = 1;
        for (int song = 0; song < songs; song++) {
            playlists = playlists * 2;
        }
        IO.println("Songs: " + songs + ", possible playlists: " + playlists);
    }
}
```

```text
Songs: 10, possible playlists: 1024
Songs: 20, possible playlists: 1048576
Songs: 30, possible playlists: 1073741824
Songs: 40, possible playlists: 1099511627776
```

```python
for songs in [10, 20, 30, 40]:
    playlists = 1
    for song in range(songs):
        playlists = playlists * 2
    print(f"Songs: {songs}, possible playlists: {playlists}")
```

```text
Songs: 10, possible playlists: 1024
Songs: 20, possible playlists: 1048576
Songs: 30, possible playlists: 1073741824
Songs: 40, possible playlists: 1099511627776
```

```javascript
for (const songs of [10, 20, 30, 40]) {
  let playlists = 1;
  for (let song = 0; song < songs; song++) {
    playlists = playlists * 2;
  }
  console.log(`Songs: ${songs}, possible playlists: ${playlists}`);
}
```

```text
Songs: 10, possible playlists: 1024
Songs: 20, possible playlists: 1048576
Songs: 30, possible playlists: 1073741824
Songs: 40, possible playlists: 1099511627776
```

```typescript
for (const songs of [10, 20, 30, 40]) {
  let playlists = 1;
  for (let song = 0; song < songs; song++) {
    playlists = playlists * 2;
  }
  console.log(`Songs: ${songs}, possible playlists: ${playlists}`);
}
```

```text
Songs: 10, possible playlists: 1024
Songs: 20, possible playlists: 1048576
Songs: 30, possible playlists: 1073741824
Songs: 40, possible playlists: 1099511627776
```

(The count includes the empty playlist with no songs at all.) C# and Java use `long` here because the answer for 40 songs is too big for an `int`; Python, JavaScript and TypeScript handle numbers this size without being asked.

A computer that checks a million playlists a second gets through 20 songs' worth in about a second. Forty songs, over a trillion playlists, take it about 13 days. Fifty songs take about 36 years.

**Buy a computer twice as fast.** It checks twice as many playlists in the same time, and that buys you exactly **one more song**, because one more song doubles the playlists.

## How it got its name: O(2ⁿ)

Doubling the count for every item is written **2ⁿ**, read "two to the n" (2 multiplied by itself n times). A program that tries every one of those combinations takes **exponential time**, written **O(2ⁿ)** and read "big O of two to the n".

That's the difference between exponential work and everything else in this lesson. With O(n log n), or even O(n²), a faster computer or a few hours' wait gets you there. With O(2ⁿ), every song you add doubles the wait, and no computer catches up.

To be honest about this one: for the playlist, there *is* a cleverer way, because song lengths are whole seconds and an hour is only 3,600 of them, so a program can track which totals it can reach instead of which playlists it can make. That technique is called dynamic programming, and it builds on Module 3's *memoization*. Plenty of "try every combination" problems have no shortcut like that, which is why the first step is always to count the combinations.

**Try it.** Add 50 and 60 to the list of song counts and run it again. Then, in C# or Java, change `long` back to `int` and see what happens to the numbers once they grow too big.

## Check yourself

2 questions to try on the lesson page.

## So what

When someone sorts data, expect O(n log n), and know that it's nearly as cheap as reading the data once. When a solution "tries every combination", count the combinations first: if the count doubles with each item, look for another way before writing a line.

## Key terms

- [Big-O Notation](https://www.ask-codey.com/glossary/big-o-notation)
- [Linearithmic Time](https://www.ask-codey.com/glossary/linearithmic-time)
- [Exponential Time](https://www.ask-codey.com/glossary/exponential-time)

## Cheat sheets

- [Sorting a Million Songs, and the Playlist You Can't Compute: O(n log n) and O(2ⁿ)](https://www.ask-codey.com/cheat-sheets/big-o-n-log-n-and-exponential-cheat-sheet)

Source: https://www.ask-codey.com/lessons/big-o-n-log-n-and-exponential
