# Will It Survive a Million Users? The Doubling Table

One table puts all six growth rates side by side at 10, 1,000 and 1,000,000 items, and shows why the growth rate of your code matters far more than the speed of your computer.

Novice · Software Development · Updated November 17, 2026

By Gregor Dzierzon

## After this lesson you can

- Use the doubling table to compare growth rates at 10, 1,000 and 1,000,000 items
- Explain why a better growth rate matters more than a faster computer
- Choose whether an approach is fast enough from its growth rate and the amount of data it will meet

## Key takeaways

- With little data, every growth rate is fast. The differences show up as the data grows.
- At a million items and a million steps a second, O(n) takes 1 second and O(n²) takes about 11 days.
- A faster computer divides the time by a fixed amount. A better growth rate can turn days into seconds.
- Whether an approach is fast enough depends on its growth rate and how much data it will meet: O(n²) is fine for 10 items and hopeless for 10 million.

Your manager asks: "The app will have a million users next year. Will the search still be fast?" You could wait a year and see. Or you could buy bigger servers now and hope. Neither tells you anything today. But you've spent this chapter giving each of the music app's complaints a growth rate, and if you know the search's growth rate, one table gives you the answer now. This is the table that makes Big-O real: the six growth rates from this chapter, side by side, at three sizes of data.

## The six growth rates so far

| Big-O | Read aloud | Name | In the music app |
|---|---|---|---|
| O(1) | big O of one | constant | play track 214 |
| O(log n) | big O of log n | logarithmic | halving the sorted catalog to find one title |
| O(n) | big O of n | linear | "is this song already in my library?" |
| O(n log n) | big O of n log n | linearithmic | sorting a million songs for the A to Z view |
| O(n²) | big O of n squared | quadratic | the "find duplicates" button |
| O(2ⁿ) | big O of two to the n | exponential | trying every playlist to fill exactly 60 minutes |

They're listed from the slowest-growing to the fastest-growing, which also means from the best to the worst when the data gets big.

## The doubling table

Say a computer does a **million steps a second** (a microsecond per step, a millionth of a second). Here is roughly how long each growth rate takes:

| Growth rate | 10 items | 1,000 items | 1,000,000 items |
|---|---|---|---|
| O(1) | a microsecond | a microsecond | a microsecond |
| O(log n) | 3 microseconds | 10 microseconds | 20 microseconds |
| O(n) | 10 microseconds | a thousandth of a second | 1 second |
| O(n log n) | 33 microseconds | a hundredth of a second | 20 seconds |
| O(n²) | a ten-thousandth of a second | 1 second | about 11 and a half days |
| O(2ⁿ) | a thousandth of a second | far longer than the age of the universe | far longer than the age of the universe |

Read it one column at a time:

- **At 10 items, everything is fast.** Even exponential time takes a thousandth of a second. This is why slow code so often works fine while you're building it.
- **At 1,000 items, the field splits.** Most rates are still well under a second, O(n²) needs a whole second, and O(2ⁿ) is out of the race for good.
- **At 1,000,000 items, it's a different world.** O(n) finishes in a second and O(n log n) in about 20. O(n²) needs more than eleven days.

## The computer does the math

You can have the computer work out the steps for a million items. The logarithm is counted by halving until one is left, rounding down this time, and adding one step for the last look: 20 for a million, as in *How Many Times Can You Halve a Million? O(log n)*.

```csharp
long n = 1000000;

long logSteps = 1;
for (long left = n; left > 1; left = left / 2)
{
    logSteps++;
}

Console.WriteLine("Items: " + n);
Console.WriteLine("constant: 1 step");
Console.WriteLine("logarithmic: " + logSteps + " steps");
Console.WriteLine("linear: " + n + " steps");
Console.WriteLine("linearithmic: " + (n * logSteps) + " steps");
Console.WriteLine("quadratic: " + (n * n) + " steps");
Console.WriteLine("Quadratic at a million steps a second: " + (n * n / 1000000 / 86400) + " days");
```

```text
Items: 1000000
constant: 1 step
logarithmic: 20 steps
linear: 1000000 steps
linearithmic: 20000000 steps
quadratic: 1000000000000 steps
Quadratic at a million steps a second: 11 days
```

```java
void main() {
    long n = 1000000;

    long logSteps = 1;
    for (long left = n; left > 1; left = left / 2) {
        logSteps++;
    }

    IO.println("Items: " + n);
    IO.println("constant: 1 step");
    IO.println("logarithmic: " + logSteps + " steps");
    IO.println("linear: " + n + " steps");
    IO.println("linearithmic: " + (n * logSteps) + " steps");
    IO.println("quadratic: " + (n * n) + " steps");
    IO.println("Quadratic at a million steps a second: " + (n * n / 1000000 / 86400) + " days");
}
```

```text
Items: 1000000
constant: 1 step
logarithmic: 20 steps
linear: 1000000 steps
linearithmic: 20000000 steps
quadratic: 1000000000000 steps
Quadratic at a million steps a second: 11 days
```

```python
n = 1000000

log_steps = 1
left = n
while left > 1:
    left = left // 2
    log_steps += 1

print(f"Items: {n}")
print("constant: 1 step")
print(f"logarithmic: {log_steps} steps")
print(f"linear: {n} steps")
print(f"linearithmic: {n * log_steps} steps")
print(f"quadratic: {n * n} steps")
print(f"Quadratic at a million steps a second: {n * n // 1000000 // 86400} days")
```

```text
Items: 1000000
constant: 1 step
logarithmic: 20 steps
linear: 1000000 steps
linearithmic: 20000000 steps
quadratic: 1000000000000 steps
Quadratic at a million steps a second: 11 days
```

```javascript
const n = 1000000;

let logSteps = 1;
for (let left = n; left > 1; left = Math.floor(left / 2)) {
  logSteps++;
}

console.log(`Items: ${n}`);
console.log("constant: 1 step");
console.log(`logarithmic: ${logSteps} steps`);
console.log(`linear: ${n} steps`);
console.log(`linearithmic: ${n * logSteps} steps`);
console.log(`quadratic: ${n * n} steps`);
console.log(`Quadratic at a million steps a second: ${Math.floor(n * n / 1000000 / 86400)} days`);
```

```text
Items: 1000000
constant: 1 step
logarithmic: 20 steps
linear: 1000000 steps
linearithmic: 20000000 steps
quadratic: 1000000000000 steps
Quadratic at a million steps a second: 11 days
```

```typescript
const n: number = 1000000;

let logSteps = 1;
for (let left = n; left > 1; left = Math.floor(left / 2)) {
  logSteps++;
}

console.log(`Items: ${n}`);
console.log("constant: 1 step");
console.log(`logarithmic: ${logSteps} steps`);
console.log(`linear: ${n} steps`);
console.log(`linearithmic: ${n * logSteps} steps`);
console.log(`quadratic: ${n * n} steps`);
console.log(`Quadratic at a million steps a second: ${Math.floor(n * n / 1000000 / 86400)} days`);
```

```text
Items: 1000000
constant: 1 step
logarithmic: 20 steps
linear: 1000000 steps
linearithmic: 20000000 steps
quadratic: 1000000000000 steps
Quadratic at a million steps a second: 11 days
```

The last line divides the steps by a million (steps per second) and then by 86,400 (seconds in a day). Exponential is left out on purpose: 2 to the power of a million has about 300,000 digits.

**Try it.** Change `n` to 1000 and run it again, then compare every line with the 1,000 column of the table. Then try 10000000 (ten million): quadratic jumps from 11 days to over 3 years.

## The picture: six curves

Draw each growth rate as a line, with the amount of data going right and the steps going up. The slow growers hug the floor; the fast growers shoot off the top.

![A chart with the amount of data across the bottom and the number of steps up the side, showing six curves labeled at their ends: O(1) flat along the floor, O(log n) barely rising, O(n) a straight diagonal line, O(n log n) a little steeper, O(n²) curving sharply upward, and O(2ⁿ) shooting almost straight up](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/9f32cf9488d54768959d41625335350b.webp)

## A faster computer or a better algorithm?

Suppose the O(n²) search takes 11 days for a million items. Buy a computer that's 10 times faster, and it takes about a day: still too slow. Rewrite it as O(n log n), and the old computer finishes in about 20 seconds.

A faster computer divides the time by a fixed number. A better growth rate changes the shape of the curve. As the data grows, the shape always wins, which is why developers care so much about Big-O.

## Check yourself

2 questions to try on the lesson page.

## So what

When someone tells you how much data is coming, the doubling table tells you which code will survive it. Keep it in mind every time you pick a structure in the rest of this course: each one is a choice about which column of this table your app lives in.

## Key terms

- [Big-O Notation](https://www.ask-codey.com/glossary/big-o-notation)
- [Growth Rate](https://www.ask-codey.com/glossary/growth-rate)
- [Time Complexity](https://www.ask-codey.com/glossary/time-complexity)

## Cheat sheets

- [Will It Survive a Million Users? The Doubling Table](https://www.ask-codey.com/cheat-sheets/big-o-doubling-table-cheat-sheet)

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