In Your Textbook: Big-O, Big-Θ and Big-Ω

What a Data Structures textbook means by Big-O, Big-Theta and Big-Omega, how to read each symbol aloud, and its formal definition of Big-O in everyday words, checked with a little code.

Journeyman · Software Development · Updated

By

After this lesson you can

  • Read Big-O, Big-Theta and Big-Omega aloud and say what each one promises
  • Explain the formal definition of Big-O in everyday words, and check it for a step count such as 3n + 5

Key takeaways

  • Big-O (O) is a ceiling: the work grows no faster than this. Big-Omega (Ω) is a floor: no slower than this. Big-Theta (Θ) is both: exactly this rate.
  • In everyday talk and in interviews, people say Big-O and usually mean the tight answer, the one a textbook writes with Θ.
  • The formal definition says: past some size n₀, the work is never more than a constant c times g(n).
  • This lesson is optional. Read it if your class or textbook uses the symbols.

This lesson is optional. Everything else in the course uses Big-O the way working developers do. But if your Data Structures class or textbook writes Θ and Ω, or asks you to "prove" that something is O(n), this is the translation from the textbook's symbols to the ideas you already have. Nothing here changes what you've learned; it puts the formal names on it.

Three promises: a ceiling, a floor, and both

Think of a delivery that's promised "within 5 days". That's a ceiling: it won't take longer, though it might come sooner. "At least 2 days" is a floor. "Between 2 and 5 days, and in practice right about 3" is both. Textbooks have a symbol for each kind of promise about how work grows:

Symbol Read aloud The promise Everyday version
O(n) "big O of n" A ceiling: grows no faster than n "Within 5 days"
Ω(n) "big Omega of n" A floor: grows no slower than n "At least 2 days"
Θ(n) "big Theta of n" Both: grows exactly like n "About 3 days, every time"

Ω is the Greek capital letter omega, and Θ is the Greek capital theta. Together, these are called asymptotic notation: "asymptotic" means "as the data gets very large", the only size where these promises are about.

Searching a playlist from the top, looking for a song that isn't there, reads every title: it's Θ(n). So it's also O(n) (no faster-growing than n) and Ω(n) (no slower-growing than n). A ceiling is allowed to be loose: it's also true, if unhelpful, to say it's O(n²). That's why a textbook uses Θ when it means "exactly this rate".

What people mean in practice

In everyday work and in interviews, people say "Big-O" and mean the tight, exact rate: what a textbook would write with Θ. If an interviewer asks for the Big-O of a search through a list, they want O(n), not O(n²), even though both are true ceilings. This course does the same, so when your textbook says Θ, read it as "the Big-O we've been using all along".

The formal definition, in everyday words

Textbooks define Big-O like this:

f(n) is O(g(n)) if there are positive constants c and n₀ such that f(n) ≤ c · g(n) for every n ≥ n₀.

Read slowly, it says three things you already know:

  • f(n) is the step count of some code, such as 3n + 5. g(n) is the simple rate you're comparing it with, such as n.
  • c is a constant multiplier: we're allowed to stretch g(n) by any fixed amount. That's the "dropping the small stuff" from Are Two Loops Twice as Slow? Why O(2n) Is Still O(n), written as a rule.
  • n₀ (read "n nought" or "n zero") is a starting size. Below it, anything goes; the promise only has to hold from n₀ on, for all bigger data.

So: past some size, the work never grows beyond a constant times g(n). That's all "O" promises.

Checking it for 3n + 5

Say some code takes 3n + 5 steps. Is it O(n)? The definition asks you to find a c and an n₀ that work. Try c = 4: is 3n + 5 ≤ 4n? The code below checks it for n from 1 to 8:

for (int n = 1; n <= 8; n++)
{
    int steps = 3 * n + 5;
    int ceiling = 4 * n;
    Console.WriteLine("n = " + n + ": 3n + 5 = " + steps + ", 4n = " + ceiling + (steps <= ceiling ? ", holds" : ", not yet"));
}
n = 1: 3n + 5 = 8, 4n = 4, not yet
n = 2: 3n + 5 = 11, 4n = 8, not yet
n = 3: 3n + 5 = 14, 4n = 12, not yet
n = 4: 3n + 5 = 17, 4n = 16, not yet
n = 5: 3n + 5 = 20, 4n = 20, holds
n = 6: 3n + 5 = 23, 4n = 24, holds
n = 7: 3n + 5 = 26, 4n = 28, holds
n = 8: 3n + 5 = 29, 4n = 32, holds
void main() {
    for (int n = 1; n <= 8; n++) {
        int steps = 3 * n + 5;
        int ceiling = 4 * n;
        IO.println("n = " + n + ": 3n + 5 = " + steps + ", 4n = " + ceiling + (steps <= ceiling ? ", holds" : ", not yet"));
    }
}
n = 1: 3n + 5 = 8, 4n = 4, not yet
n = 2: 3n + 5 = 11, 4n = 8, not yet
n = 3: 3n + 5 = 14, 4n = 12, not yet
n = 4: 3n + 5 = 17, 4n = 16, not yet
n = 5: 3n + 5 = 20, 4n = 20, holds
n = 6: 3n + 5 = 23, 4n = 24, holds
n = 7: 3n + 5 = 26, 4n = 28, holds
n = 8: 3n + 5 = 29, 4n = 32, holds
for n in range(1, 9):
    steps = 3 * n + 5
    ceiling = 4 * n
    result = "holds" if steps <= ceiling else "not yet"
    print(f"n = {n}: 3n + 5 = {steps}, 4n = {ceiling}, {result}")
n = 1: 3n + 5 = 8, 4n = 4, not yet
n = 2: 3n + 5 = 11, 4n = 8, not yet
n = 3: 3n + 5 = 14, 4n = 12, not yet
n = 4: 3n + 5 = 17, 4n = 16, not yet
n = 5: 3n + 5 = 20, 4n = 20, holds
n = 6: 3n + 5 = 23, 4n = 24, holds
n = 7: 3n + 5 = 26, 4n = 28, holds
n = 8: 3n + 5 = 29, 4n = 32, holds
for (let n = 1; n <= 8; n++) {
  const steps = 3 * n + 5;
  const ceiling = 4 * n;
  console.log(`n = ${n}: 3n + 5 = ${steps}, 4n = ${ceiling}, ${steps <= ceiling ? "holds" : "not yet"}`);
}
n = 1: 3n + 5 = 8, 4n = 4, not yet
n = 2: 3n + 5 = 11, 4n = 8, not yet
n = 3: 3n + 5 = 14, 4n = 12, not yet
n = 4: 3n + 5 = 17, 4n = 16, not yet
n = 5: 3n + 5 = 20, 4n = 20, holds
n = 6: 3n + 5 = 23, 4n = 24, holds
n = 7: 3n + 5 = 26, 4n = 28, holds
n = 8: 3n + 5 = 29, 4n = 32, holds
for (let n = 1; n <= 8; n++) {
  const steps: number = 3 * n + 5;
  const ceiling: number = 4 * n;
  console.log(`n = ${n}: 3n + 5 = ${steps}, 4n = ${ceiling}, ${steps <= ceiling ? "holds" : "not yet"}`);
}
n = 1: 3n + 5 = 8, 4n = 4, not yet
n = 2: 3n + 5 = 11, 4n = 8, not yet
n = 3: 3n + 5 = 14, 4n = 12, not yet
n = 4: 3n + 5 = 17, 4n = 16, not yet
n = 5: 3n + 5 = 20, 4n = 20, holds
n = 6: 3n + 5 = 23, 4n = 24, holds
n = 7: 3n + 5 = 26, 4n = 28, holds
n = 8: 3n + 5 = 29, 4n = 32, holds

From n = 5 on, 3n + 5 never passes 4n: each step up adds 3 to the left side and 4 to the right, so the ceiling only pulls further ahead. So c = 4 and n₀ = 5 work, and 3n + 5 is O(n). That's what a textbook proof looks like: name a c and an n₀, and show the inequality holds from there on. (A printout of eight rows isn't a proof by itself; the "adds 3, adds 4" reasoning is.)

A chart with n across the bottom from 1 to 8, showing the line 3n + 5 starting above the line 4n, the two meeting at n = 5, and 4n above 3n + 5 from there on, with the region from n = 5 onward shaded and labeled "from n₀ = 5 on, 3n + 5 ≤ 4n"

Try it. Is 3n + 5 also O(n) with c = 6? Change the 4 to a 6 and find the smallest n₀ that works now. (A bigger c is allowed, and makes n₀ smaller.)

Check yourself

2 questions to try on the lesson page.

So what

When your textbook writes Θ(n log n) or asks for a c and an n₀, you now know it's the same idea as the rest of this course, written in its formal form. And in an interview or at work, "Big-O" means the exact, tight growth rate, which is what you've been finding all along.

Key terms

Cheat sheets