Big O in Plain English

The problem

Your solution passes the small examples, then times out on the hidden test with 100,000 numbers. Or an interviewer asks, "What's the time complexity?" and you're not sure how to answer. Big O is the shared language for "how does this code behave when the input gets big?"

Real-world analogy

Imagine finding a friend's name:

• In a phone contacts search, you type the name and it appears. The time hardly changes whether you have 50 contacts or 5,000. That's constant time, O(1).
• In a printed phone book, you open the middle, then the middle of the half, and so on. Doubling the book adds just one more step. That's O(log n).
• In a shoebox of unsorted business cards, you check every card. Twice the cards, twice the time. That's O(n).
• If you had to compare every card with every other card to find duplicates, twice the cards means four times the work. That's O(n²).

The idea

Big O counts how the number of steps grows with the input size n, ignoring constants and small details. These six cover almost every interview problem:

How to read it from code:

• One loop over the input → O(n).
• A loop inside a loop, both over the input → O(n²).
• Halving the search space each step → O(log n).
• Loops one after another add up: O(n) + O(n) is still O(n).
• Sorting costs O(n log n), so "sort first" sets a floor.

Space complexity is the same idea for memory. A seen dictionary that may hold every element is O(n) extra space.

Rule of thumb for coding tests: about 10⁸ simple steps per second is the most you can expect. With n = 100,000, O(n²) is 10¹⁰ steps (too slow), while O(n log n) is about 1.7 million (instant).

The code

Counting steps makes Big O concrete. This example counts how many times each approach does its core work as the list grows.

def count_pairs_steps(n):
    steps = 0
    for i in range(n):           # loop inside a loop: O(n^2)
        for j in range(i + 1, n):
            steps += 1
    return steps


def count_single_loop_steps(n):
    steps = 0
    for i in range(n):           # one loop: O(n)
        steps += 1
    return steps


def count_halving_steps(n):
    steps = 0
    while n > 1:                 # halve each time: O(log n)
        n //= 2
        steps += 1
    return steps


for n in [10, 100, 1000, 10000]:
    print(f"n={n:>5}  halving={count_halving_steps(n):>2}  "
          f"one loop={count_single_loop_steps(n):>5}  all pairs={count_pairs_steps(n):>8}")

n=   10  halving= 3  one loop=   10  all pairs=      45
n=  100  halving= 6  one loop=  100  all pairs=    4950
n= 1000  halving= 9  one loop= 1000  all pairs=  499500
n=10000  halving=13  one loop=10000  all pairs=49995000

function countPairsSteps(n) {
  let steps = 0;
  for (let i = 0; i < n; i++) {          // loop inside a loop: O(n^2)
    for (let j = i + 1; j < n; j++) steps++;
  }
  return steps;
}

function countSingleLoopSteps(n) {
  let steps = 0;
  for (let i = 0; i < n; i++) steps++;   // one loop: O(n)
  return steps;
}

function countHalvingSteps(n) {
  let steps = 0;
  while (n > 1) {                        // halve each time: O(log n)
    n = Math.floor(n / 2);
    steps++;
  }
  return steps;
}

const pad = (v, w) => String(v).padStart(w);
for (const n of [10, 100, 1000, 10000]) {
  console.log(`n=${pad(n, 5)}  halving=${pad(countHalvingSteps(n), 2)}  ` +
    `one loop=${pad(countSingleLoopSteps(n), 5)}  all pairs=${pad(countPairsSteps(n), 8)}`);
}

n=   10  halving= 3  one loop=   10  all pairs=      45
n=  100  halving= 6  one loop=  100  all pairs=    4950
n= 1000  halving= 9  one loop= 1000  all pairs=  499500
n=10000  halving=13  one loop=10000  all pairs=49995000

Going from 1,000 to 10,000 items, halving adds 4 steps, one loop does 10 times more, and all pairs does about 100 times more. That gap is why patterns matter.

Common mistakes

• Counting a hidden loop as O(1). x in my_list (Python) and array.includes(x) (JavaScript) scan the list: O(n). Inside a loop, that's O(n²). Use a set or map for O(1) lookups.
• Forgetting the cost of sorting. A one-loop solution after sort() is O(n log n), not O(n).
• Reporting best-case speed. Big O normally describes the worst case unless you say otherwise.
• Ignoring space. Saying "O(n) extra space" for a seen map shows you thought about memory too.

Key points

• Big O describes growth, not exact speed: how steps increase as n grows.
• One loop is O(n), nested loops O(n²), halving O(log n), sorting O(n log n).
• Set and dictionary/map lookups are O(1) on average; list searches are O(n).
• Check the input size: n = 100,000 rules out O(n²), which tells you a faster pattern is expected.