# How Many Times Can You Halve a Million? O(log n)

Find one song among a million sorted titles in about 20 looks instead of a million, and name the growth rate that makes it possible: O(log n), logarithmic time.

Novice · Software Development · Updated November 17, 2026

By Gregor Dzierzon

## After this lesson you can

- Explain O(log n) as cutting what's left in half at every step
- Work out roughly how many halvings it takes to get from a number down to 1

## Key takeaways

- A logarithm answers "how many times can I cut this in half before one is left?" For 1,000,000 it's 20.
- O(log n), read "big O of log n", is logarithmic time: doubling the data adds only one more step.
- Halving only works when the data is in order, like a sorted list or the numbers 1 to 100.
- Reading from either end, or jumping ahead 1,000 titles at a time, still grows with the list; only halving keeps a million songs to about 20 looks.

**Before this:** *Why the Library Check Slows Down and Play Doesn't: O(1) and O(n)* (a check that reads every title grows with the library).

The music app's catalog has a million songs, kept in A to Z order, and a search box that jumps to a title as you type it. Today the search reads titles from the top. One search of a million titles takes a laptop about a hundredth of a second in Python, which sounds fine, until you remember that the app's server runs one for every keystroke of every user. At a thousand keystrokes a second, that's ten seconds of reading every second, and the server falls further behind with every song the catalog adds. The list is already sorted. Can that help?

## What would you try?

**Read from the top.** A title near Z takes almost a million looks, and one that isn't there takes all of them. O(n).

**Read from the end.** Now Z is quick and A is slow. On average it's the same half a million looks.

**Jump ahead 1,000 titles at a time, then step back.** Because the list is sorted, you can jump: look at title 1,000, then 2,000, then 3,000, until you pass the one you want, then walk back through the last 1,000. That's at most 1,000 jumps and 999 steps back: about 2,000 looks instead of a million. Much better! But double the catalog and the jumps double too. It still grows with n.

| What we tried | Looks for one title, at most, in 1,000,000 | In 2,000,000 |
|---|---|---|
| Read from the top | 1,000,000 | 2,000,000 |
| Read from the end | 1,000,000 | 2,000,000 |
| Jump 1,000 at a time, then step back | about 2,000 | about 3,000 |

## The questions that lead to it

**The list is sorted. Look once, at the middle title. What do you know now?** If the title you want comes before it, it's in the first half; if after, the second. Either way, one look has thrown away **half the list**: 500,000 songs you never need to read.

**How many are left after 2 looks?** A quarter: 250,000. **After 10?** About a thousand. **After 20?** One song.

So the real question is: **how many times can you halve a million before one is left?**

The code below counts it, for a thousand songs, a million and a billion. Each halving keeps the bigger half, rounded up, because the song you want could be in it:

```csharp
foreach (int songs in new int[] { 1000, 1000000, 1000000000 })
{
    int left = songs;
    int halvings = 0;
    while (left > 1)
    {
        left = (left + 1) / 2;
        halvings++;
    }
    Console.WriteLine("Songs: " + songs + ", halvings to get down to one: " + halvings);
}
```

```text
Songs: 1000, halvings to get down to one: 10
Songs: 1000000, halvings to get down to one: 20
Songs: 1000000000, halvings to get down to one: 30
```

```java
void main() {
    for (int songs : new int[] { 1000, 1000000, 1000000000 }) {
        int left = songs;
        int halvings = 0;
        while (left > 1) {
            left = (left + 1) / 2;
            halvings++;
        }
        IO.println("Songs: " + songs + ", halvings to get down to one: " + halvings);
    }
}
```

```text
Songs: 1000, halvings to get down to one: 10
Songs: 1000000, halvings to get down to one: 20
Songs: 1000000000, halvings to get down to one: 30
```

```python
for songs in [1000, 1000000, 1000000000]:
    left = songs
    halvings = 0
    while left > 1:
        left = (left + 1) // 2
        halvings += 1
    print(f"Songs: {songs}, halvings to get down to one: {halvings}")
```

```text
Songs: 1000, halvings to get down to one: 10
Songs: 1000000, halvings to get down to one: 20
Songs: 1000000000, halvings to get down to one: 30
```

```javascript
for (const songs of [1000, 1000000, 1000000000]) {
  let left = songs;
  let halvings = 0;
  while (left > 1) {
    left = Math.floor((left + 1) / 2);
    halvings++;
  }
  console.log(`Songs: ${songs}, halvings to get down to one: ${halvings}`);
}
```

```text
Songs: 1000, halvings to get down to one: 10
Songs: 1000000, halvings to get down to one: 20
Songs: 1000000000, halvings to get down to one: 30
```

```typescript
for (const songs of [1000, 1000000, 1000000000]) {
  let left = songs;
  let halvings = 0;
  while (left > 1) {
    left = Math.floor((left + 1) / 2);
    halvings++;
  }
  console.log(`Songs: ${songs}, halvings to get down to one: ${halvings}`);
}
```

```text
Songs: 1000, halvings to get down to one: 10
Songs: 1000000, halvings to get down to one: 20
Songs: 1000000000, halvings to get down to one: 30
```

C#, Java and Python drop the remainder when they divide two whole numbers this way (`//` in Python), while JavaScript and TypeScript need `Math.floor` to round down. Adding 1 before halving is what rounds up, so the bigger half is kept.

Twenty looks for a million songs, against 2,000 for the best of the tries. And a thousand times more songs, a billion, adds only 10 more.

![A long bar labeled 1,000,000 songs, halved again and again in rows beneath it: 500,000, then 250,000, then 125,000 and so on, each bar half as long as the one above, down to a single song after 20 halvings](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/622a66b9a6bf4617b99622b6e6fa17b5.webp)

**Try it.** Play the halving game with a friend. They think of a number from 1 to 100; you guess the middle, and they say "higher" or "lower". However the game goes, you'll never need more than 7 guesses: add 100 to the code's list of sizes to see why. Turning this game into a real search, with its tricky edges, is *One Song in a Million, in 20 Looks: Binary Search* in Module 4.

## How it got its name

The number of times you can cut something in half before one is left was so useful that it got a name: its **logarithm**, or **log** for short. In this course, "log" always means halving (in your textbook, the **base-2 logarithm**, written log₂ and read "log base two"). You don't need a formula; you need the idea:

| How much data | Halvings to get down to 1 (about) |
|---|---|
| 100 | 7 |
| 1,000 | 10 |
| 1,000,000 | 20 |
| 1,000,000,000 | 30 |

Work that grows like that, by one step every time the data doubles, is called **logarithmic time**. It's written **O(log n)** and read "big O of log n". After O(1), it's the slowest-growing rate you'll meet: a search that halves stays fast however big the catalog gets.

There's a catch, and it matters: halving only works when the data is **in order**. "Before the middle title" tells you something only because the titles are in A to Z order. A jumbled list can't be halved; it can only be read.

## Check yourself

2 questions to try on the lesson page.

## So what

Whenever a program throws away half of what's left at each step, it stays fast however big the data gets. That's why sorted data and search trees are worth the effort, and why "can I halve it?" is a question worth asking about every slow search.

## Key terms

- [Big-O Notation](https://www.ask-codey.com/glossary/big-o-notation)
- [Logarithm](https://www.ask-codey.com/glossary/logarithm)
- [Logarithmic Time](https://www.ask-codey.com/glossary/logarithmic-time)

## Cheat sheets

- [How Many Times Can You Halve a Million? O(log n)](https://www.ask-codey.com/cheat-sheets/big-o-logarithmic-cheat-sheet)

Source: https://www.ask-codey.com/lessons/big-o-logarithmic
