Are Two Loops Twice as Slow? Why O(2n) Is Still O(n)

Big-O keeps only the part of the step count that grows fastest and drops the rest, so 2n steps is O(n) and n² + n steps is O(n²). Here's why, and when the small stuff still matters.

Apprentice · Software Development · Updated

By

After this lesson you can

  • Simplify a step count to its Big-O by keeping only the fastest-growing part
  • Explain when the parts Big-O drops still matter in real code

Key takeaways

  • To get the Big-O from a step count, keep the fastest-growing part and drop the rest, along with any number it's multiplied by.
  • 2n, 3n + 5 and n ÷ 2 are all O(n): each one doubles when n doubles.
  • Code with the same Big-O can still be twice as fast as other code. Big-O tells you how the work grows, not every detail of how long it takes.

In a code review, a teammate points at your function: "It goes through the playlist twice. Isn't that twice as slow? Shouldn't it be O(2n)?" You count its steps and get "2n + 3". A classmate counts a different function and gets "n² + n". Neither of you writes O(2n + 3) or O(n² + n) in the answer. Big-O has one simplifying rule, and once you know it, every step count you meet turns into one of the six growth rates from Will It Survive a Million Users? The Doubling Table. Textbooks, interviews and code reviews all use the short form, so this is the rule that lets you read and write it, and answer your teammate.

Two loops in a row

A music app shows the shortest and the longest song on a playlist. One way is to go through the playlist twice: once to find the shortest song, once to find the longest. That's n steps, then n more: 2n steps.

Another way does both in one loop: n steps. Here are both, with a counter for every song looked at. The song lengths are made up (in seconds), between 120 and 299:

List<int> MakeLengths(int songCount)
{
    List<int> lengths = new List<int>();
    for (int i = 0; i < songCount; i++)
    {
        lengths.Add(120 + (i * 7) % 180);
    }
    return lengths;
}

int TwoLoops(List<int> lengths)
{
    int looks = 0;
    int shortest = lengths[0];
    foreach (int length in lengths)
    {
        looks++;
        if (length < shortest) shortest = length;
    }
    int longest = lengths[0];
    foreach (int length in lengths)
    {
        looks++;
        if (length > longest) longest = length;
    }
    return looks;
}

int OneLoop(List<int> lengths)
{
    int looks = 0;
    int shortest = lengths[0];
    int longest = lengths[0];
    foreach (int length in lengths)
    {
        looks++;
        if (length < shortest) shortest = length;
        if (length > longest) longest = length;
    }
    return looks;
}

foreach (int songCount in new int[] { 1000, 2000, 4000 })
{
    List<int> lengths = MakeLengths(songCount);
    Console.WriteLine("Songs: " + songCount + ", two loops: " + TwoLoops(lengths) + " looks, one loop: " + OneLoop(lengths) + " looks");
}
Songs: 1000, two loops: 2000 looks, one loop: 1000 looks
Songs: 2000, two loops: 4000 looks, one loop: 2000 looks
Songs: 4000, two loops: 8000 looks, one loop: 4000 looks
List<Integer> makeLengths(int songCount) {
    List<Integer> lengths = new ArrayList<>();
    for (int i = 0; i < songCount; i++) {
        lengths.add(120 + (i * 7) % 180);
    }
    return lengths;
}

int twoLoops(List<Integer> lengths) {
    int looks = 0;
    int shortest = lengths.get(0);
    for (int length : lengths) {
        looks++;
        if (length < shortest) shortest = length;
    }
    int longest = lengths.get(0);
    for (int length : lengths) {
        looks++;
        if (length > longest) longest = length;
    }
    return looks;
}

int oneLoop(List<Integer> lengths) {
    int looks = 0;
    int shortest = lengths.get(0);
    int longest = lengths.get(0);
    for (int length : lengths) {
        looks++;
        if (length < shortest) shortest = length;
        if (length > longest) longest = length;
    }
    return looks;
}

void main() {
    for (int songCount : new int[] {1000, 2000, 4000}) {
        List<Integer> lengths = makeLengths(songCount);
        IO.println("Songs: " + songCount + ", two loops: " + twoLoops(lengths) + " looks, one loop: " + oneLoop(lengths) + " looks");
    }
}
Songs: 1000, two loops: 2000 looks, one loop: 1000 looks
Songs: 2000, two loops: 4000 looks, one loop: 2000 looks
Songs: 4000, two loops: 8000 looks, one loop: 4000 looks
def make_lengths(song_count):
    lengths = []
    for i in range(song_count):
        lengths.append(120 + (i * 7) % 180)
    return lengths


def two_loops(lengths):
    looks = 0
    shortest = lengths[0]
    for length in lengths:
        looks += 1
        if length < shortest:
            shortest = length
    longest = lengths[0]
    for length in lengths:
        looks += 1
        if length > longest:
            longest = length
    return looks


def one_loop(lengths):
    looks = 0
    shortest = lengths[0]
    longest = lengths[0]
    for length in lengths:
        looks += 1
        if length < shortest:
            shortest = length
        if length > longest:
            longest = length
    return looks


for song_count in [1000, 2000, 4000]:
    lengths = make_lengths(song_count)
    print(f"Songs: {song_count}, two loops: {two_loops(lengths)} looks, one loop: {one_loop(lengths)} looks")
Songs: 1000, two loops: 2000 looks, one loop: 1000 looks
Songs: 2000, two loops: 4000 looks, one loop: 2000 looks
Songs: 4000, two loops: 8000 looks, one loop: 4000 looks
function makeLengths(songCount) {
  const lengths = [];
  for (let i = 0; i < songCount; i++) {
    lengths.push(120 + (i * 7) % 180);
  }
  return lengths;
}

function twoLoops(lengths) {
  let looks = 0;
  let shortest = lengths[0];
  for (const length of lengths) {
    looks++;
    if (length < shortest) shortest = length;
  }
  let longest = lengths[0];
  for (const length of lengths) {
    looks++;
    if (length > longest) longest = length;
  }
  return looks;
}

function oneLoop(lengths) {
  let looks = 0;
  let shortest = lengths[0];
  let longest = lengths[0];
  for (const length of lengths) {
    looks++;
    if (length < shortest) shortest = length;
    if (length > longest) longest = length;
  }
  return looks;
}

for (const songCount of [1000, 2000, 4000]) {
  const lengths = makeLengths(songCount);
  console.log(`Songs: ${songCount}, two loops: ${twoLoops(lengths)} looks, one loop: ${oneLoop(lengths)} looks`);
}
Songs: 1000, two loops: 2000 looks, one loop: 1000 looks
Songs: 2000, two loops: 4000 looks, one loop: 2000 looks
Songs: 4000, two loops: 8000 looks, one loop: 4000 looks
function makeLengths(songCount: number): number[] {
  const lengths: number[] = [];
  for (let i = 0; i < songCount; i++) {
    lengths.push(120 + (i * 7) % 180);
  }
  return lengths;
}

function twoLoops(lengths: number[]): number {
  let looks = 0;
  let shortest = lengths[0];
  for (const length of lengths) {
    looks++;
    if (length < shortest) shortest = length;
  }
  let longest = lengths[0];
  for (const length of lengths) {
    looks++;
    if (length > longest) longest = length;
  }
  return looks;
}

function oneLoop(lengths: number[]): number {
  let looks = 0;
  let shortest = lengths[0];
  let longest = lengths[0];
  for (const length of lengths) {
    looks++;
    if (length < shortest) shortest = length;
    if (length > longest) longest = length;
  }
  return looks;
}

for (const songCount of [1000, 2000, 4000]) {
  const lengths = makeLengths(songCount);
  console.log(`Songs: ${songCount}, two loops: ${twoLoops(lengths)} looks, one loop: ${oneLoop(lengths)} looks`);
}
Songs: 1000, two loops: 2000 looks, one loop: 1000 looks
Songs: 2000, two loops: 4000 looks, one loop: 2000 looks
Songs: 4000, two loops: 8000 looks, one loop: 4000 looks

(These functions only count their looks, so the shortest and longest lengths they find are thrown away; a real app would return them.) Ask the one question from Twice the Stuff, How Much More Work? about each: when the songs double, the two-loop version's looks double, and so do the one-loop version's. Both grow the same way, so both are O(n). The 2 in 2n doesn't change the answer to the question, so Big-O drops it.

The rule: keep the part that grows fastest

To turn a step count into its Big-O:

  1. Keep only the part that grows fastest as n gets big. It's called the dominant term: the part that ends up doing nearly all the work.
  2. Drop any number it's multiplied or divided by. That number is called a constant factor.
Step count Keep the fastest-growing part Drop its number Big-O
2n 2n n O(n)
3n + 5 3n n O(n)
n ÷ 2 n ÷ 2 n O(n)
n² + n n² n² O(n²)
n² ÷ 2 − n ÷ 2 (the handshakes) n² ÷ 2 n² O(n²)
5 5 1 O(1)

The last row is how every fixed amount of work becomes O(1): 5 steps, or 500, is still "the same however much data".

Why the small stuff fades away

Take n² + n with a million songs. The n² part is a million million steps. The n part is a million. Next to the n² part, the n part is one ten-thousandth of a percent: a rounding error. It's like the price of a house plus the parking fee at the open house. You'd say the house costs "about the price of the house".

Two bars at a million items: a towering bar for n squared, a million million steps, and beside it a bar for n, a million steps, so thin it barely shows: when n is large, the smaller part is lost next to the largest one

Try it. Write down the step count for each, then its Big-O: a function that reads the playlist three times; a function with one loop over the playlist and then 10 extra steps; a nested loop over the playlist followed by one more ordinary loop. (Answers: 3n, so O(n); n + 10, so O(n); n² + n, so O(n²).)

When the small stuff still matters

Big-O answers "how does the work grow?" It doesn't answer "which one is faster today?" Three cases where the dropped parts matter:

  • The same Big-O isn't the same speed. The one-loop version above does half the looks of the two-loop version. Both are O(n), but if the playlist has 10 million songs, users notice the difference.
  • Small data. For 20 items, an O(n²) method with simple steps can beat an O(n log n) method with complicated ones. Your language's built-in sort switches to a simple method for small lists for exactly this reason.
  • Expensive steps. If each step of one method reads from a disk or the network and each step of the other reads from memory, the "same" number of steps can mean seconds against microseconds.

Use Big-O to choose the right growth rate first. Then, if it's still too slow, measure and tune the details: Is It Really Slow? Measure Your Own Code shows how.

Check yourself

2 questions to try on the lesson page.

So what

Every Big-O you'll read in a textbook, in documentation or in an interview answer is a step count with the small stuff dropped. When you can do that yourself, you can turn any loop you write into one of six familiar answers, and you know which details are still worth a second look.

Key terms

Cheat sheets