1. The problem
In the first lessons you learned the basic tools: variables (boxes for data), loops (repeating steps) and if/else choices. You can use them so that a program runs fast, or so that it runs slowly. Big-O helps you tell the two apart.
While the data is small, the fast way and the slow way both feel instant. When the data is big, the slow way can take days, and the fast way still finishes in a blink.
In the last lesson you looked for a name among a million in two ways. The first went one page at a time: up to a million looks. The second threw away half each time: about twenty looks. Same job, huge difference.
Now we give these speeds a name, so we can talk about them without drawing a table every time. The name is Big-O (read "big O"). Behind the notation is one question: when the input gets bigger, how fast does the work grow?
2. In plain words
Big-O tells you how much extra work you get when the data grows.
Seconds and clocks don't matter here. Ask yourself one question: if the data becomes twice as big, how many times more work is it?
Example: a party. If every guest shakes hands with every other guest, twice as many guests means about four times as many handshakes. 10 guests make 45 handshakes, 20 guests make 190. That kind of work grows fast. To take the 5th name from the guest list by its number, one look is enough, whether the list has 10 names or 10,000. That kind of work barely grows.
Big-O gives each kind of growth a short name. With it you can spot a slow plan in advance, before you start writing it.
3. The idea
Call the size of the input n. It just means "how many items you have". Big-O says how the work grows as n grows. Four names cover almost everything in this course:
- O(1): constant. The work is the same for any
n. Readinglist[5]is one step, whether the list has 10 items or 10 million. - O(log n): logarithm, which is how many times
ncan be halved until 1 is left. The work barely grows. This is the halving from the last lesson: a million items, about twenty steps. - O(n): linear growth. You look at each item once, so the work grows with the data. Twice the data, twice the work.
- O(n2): square. For each item you go through all the items again. For 1,000 items that is 1,000 × 1,000 = a million steps. Twice the data, four times the work. This one gets slow very quickly.
You don't need a stopwatch for this. On a fast computer the slow way only becomes a little less slow. Big-O tells you, before you run anything, which ways still work when the data gets big.
4. Read the limit, then pick the shape
Here Big-O starts to pay off. A problem almost always says how big the input can get. That number tells you which ways will work:
| the biggest the data gets | what you can afford |
|---|---|
| up to a few thousand | O(n2): a loop inside a loop is fine |
| up to a million | O(n log n) or O(n): one pass, sorting, lookup by key (Map, covered later) |
| up to a billion | O(log n) or a direct formula: even looking at every item once is too slow |
You can also read the table backwards to catch a mistake early. Say n is a million and your plan is a loop inside a loop. A million times a million is a trillion steps, and the program won't finish in the time allowed. So, before you write a line of code, the limit tells you that you need one pass over the data, and two nested loops won't fit.
Example. A night job processes 500,000 lines of log (a file where a program writes down events). A loop inside a loop gives 500,000 × 500,000 = 250 billion steps. That is hopeless. Sorting plus one pass gives about 500,000 × 19 ≈ 9.5 million steps, which is fine (19 here is log2 of 500,000). So the target is O(n log n), and you can drop every O(n2) idea.
5. Where this shows up
An experienced engineer checks the growth of the work first when a job "suddenly got slow" after its data grew. The same check helps in other cases:
- estimating the cost of a database query before shipping it to production (the live system people use);
- deciding whether a report runs right away or moves to a background job;
- spotting an accidental nested loop over a big table in code review (colleagues checking your code), before it brings production down.
Reading the input size and picking a way to match it takes five seconds. The habit saves you from writing the wrong algorithm and finding out only in production. The rest of this course teaches you to stay on the cheap side of that table.
On LeetCode
Every LeetCode problem states how big the input can get, so read that limit first. When n is a few hundred or a few thousand, a loop inside a loop is fast enough, and these problems pass with exactly that.
n is at most 100, so checking every pair with two nested loops is about 5,000 steps.
n is at most 500, so comparing each number with all the others is 250,000 steps and passes easily.
n is at most 10^4, so trying all pairs, about 50 million checks, still passes; lesson 18 does it in one pass.
Fix it yourself (Tier 2)
In this lesson you look for a bug in finished code. The editor has the function predictComplexity(n). It takes an input size and returns the slowest class that still finishes in time for that size, as a short text like "O(n log n)". In code the square is written as "O(n^2)": the ^ sign means "to the power of".
The code works, but it has one bug left on purpose: an off-by-one at the boundary. In one place it uses < (less than) where it should use <= (less than or equal). Because of that, a size that lands exactly on the boundary gets the wrong class.
You already know where to look: the comparisons with the boundaries. Read the function, find the wrong comparison, fix it, and run the tests again. One of the tests checks a size exactly on the boundary, so it points straight at the bug.
For people who already code. This is the "read the limit first" habit, written down. If you have done contest programming, nothing here is new. The value is in making one move automatic: turn
ninto a target class before you choose an approach. Skim it, fix the off-by-one, move on. One distinction is worth stating: Big-O is not benchmarking. A benchmark measures one machine, on one input, on one day. Big-O tells you that an O(n2) plan on a million rows is too slow on every machine, with nothing to run.
Practice
predictComplexity
predictComplexity(n) -> string (one of "O(n^2)","O(n log n)","O(log n)")
// Step 09: Big-O and reading constraints. Tier 2: fix the bug left in on purpose.
//
// predictComplexity(n)
// n: input size
// returns one of "O(n^2)", "O(n log n)", "O(log n)": the slowest
// complexity class that still finishes in time for that input size
// (the table in the lesson).
//
// Bug: the boundary comparisons of predictComplexity have an off-by-one.
// One threshold uses `<` where it should use `<=`, so an input sitting
// exactly on that edge gets classified one class too fast. Find it, fix it.
//
// Run: node solution.test.js
export function predictComplexity(n) {
if (n <= 5000) return 'O(n^2)';
if (n < 1000000) return 'O(n log n)';
return 'O(log n)';
}
Running as a guest
The tests run right here, no account needed. Your code is kept in this browser only. A free account keeps it on every device, marks the step done and shows where you are in the course.
Hint ladder
Stuck? Reveal one rung at a time, but try it yourself first.