cf.completefrontend
FOUNDATIONS · FOUNDATION

Big O notation

A short way to say how the work an algorithm does grows as its input gets bigger.

Time O(1), O(n), O(n^2), O(log n) for the four functionsSpace O(1) for all four2 practice problemsStep-through picture

The idea

Big O notation describes how much work code does as the input grows. It does not measure seconds. It counts steps, such as how many times a loop runs, and asks: if the input gets 10 times bigger, how many more steps does the code take?

We write the answer with the letter n for the size of the input. O(1) means the work stays the same no matter how big n is. O(n) means the work grows in step with n. O(n^2) means doubling n makes four times the work. O(log n) means doubling n adds only one more step.

Big O keeps only the part that grows fastest and drops fixed numbers. A loop that runs 3n + 5 times is still O(n), because for a big n the 3 and the 5 don't change the shape of the growth. This lets you compare two ideas before you write either one.

An everyday example

Finding a friend at a concert

You arrive at a concert and want to find your friend. If they texted you their seat number, you walk straight there: the size of the crowd doesn't matter. If you don't know where they are, you walk past every seat, so a crowd twice as big takes twice as long. If you decide to introduce every person to every other person, a crowd twice as big takes four times as long. If the seats are numbered and an usher keeps telling you "your friend is in the left half of what's left", a crowd twice as big takes just one more question.

How the example maps to the code
In the exampleIn the code
Walking straight to a known seatO(1): items[0]
Walking past every seat onceO(n): one for loop over items
Introducing every pair of peopleO(n^2): a loop inside a loop
Asking the usher which half to searchO(log n): n = Math.floor(n / 2) until n is 1

From the slow way to big o notation

  1. Start with the obvious way to compare two pieces of code: run both and time them. The number you get depends on the computer, the browser, the other open tabs, and the input you happened to try. A result like "3 milliseconds" tells you nothing about what happens when the input is 100 times bigger.
  2. So count steps instead of seconds. A step is one small action: read one slot, add two numbers, compare two values. linearTime does one addition per item, so 6 items cost 6 steps and 12 items cost 12 steps. A step count depends only on the input, so it is the same on every machine.
  3. Exact counts are still more detail than you need. quadraticTime does n * (n - 1) / 2 steps, and a slightly different version might do n * n. Both grow by about 4 times when n doubles, and that is the fact that decides whether a page freezes. So the useful question is: when n doubles, what happens to the count?
  4. There are only a few common answers: the count stays the same, it goes up by one, it doubles, or it grows about four times. Give each family the name of its simplest formula: O(1), O(log n), O(n), O(n^2). Keeping only the family and dropping the fixed numbers: that way of counting is Big O notation.

How it works

  1. Pick what n means: the length of items, the number of rows, or the value of n itself.
  2. Find the lines that run the most. Those are usually inside the deepest loop.
  3. Count how many times they run in terms of n. One loop over items runs n times. A loop inside a loop runs about n * n times.
  4. If a loop cuts n in half each time, as in n = Math.floor(n / 2), it runs about log n times.
  5. Keep only the fastest-growing part and drop fixed numbers: n^2 + 3n + 7 becomes O(n^2).
  6. Do the same for memory: count how much extra space the code creates, such as a new array of size n.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function constantTime(items) {
  2. return items[0];
  3. }
  5. function linearTime(items) {
  6. let total = 0;
  7. for (const item of items) total += item;
  8. return total;
  9. }
  11. function quadraticTime(items) {
  12. let pairs = 0;
  13. for (let i = 0; i < items.length; i++) {
  14. for (let j = i + 1; j < items.length; j++) pairs++;
  15. }
  16. return pairs;
  17. }
  19. function logarithmicTime(n) {
  20. let steps = 0;
  21. while (n > 1) {
  22. n = Math.floor(n / 2);
  23. steps++;
  24. }
  25. return steps;
  26. }

How fast it is

TimeO(1), O(n), O(n^2), O(log n) for the four functions
Extra memoryO(1) for all four

Count how many times the busiest line runs: once, once per item, once per pair of items, or once per halving. None of the functions creates anything that grows with the input.

  • Best caseO(1)

    constantTime on any list: it reads items[0] once, whether items has 3 or 3 million entries. Code that can stop early, like a search that finds its target first, also has an O(1) best case.

  • Average caseO(n)

    linearTime on any list: its loop always runs exactly n times, so its best, average, and worst cases are all the same. Cases only differ for code that can stop early or skip work depending on the values.

  • Worst caseO(n^2)

    quadraticTime, the slowest of the four: it always counts n * (n - 1) / 2 pairs, 499,500 of them for 1,000 items, whatever the values are.

Common mistakes

  • Thinking O(n) code is always faster than O(n^2) code. For 5 items the difference is tiny; Big O describes what happens as n grows large.
  • Missing hidden loops. array.includes(x), array.indexOf(x), and array.slice() each walk the array, so calling includes inside a for loop is O(n^2), not O(n).
  • Adding instead of multiplying. Two loops one after the other are O(n + n) = O(n); one loop inside the other is O(n * n).
  • Forgetting memory. Building a new array or Map of all the input is O(n) extra space, even if the time is fine.

When to use it

Look for these clues in a problem:

  • A problem gives limits like n <= 100000 and you need to know whether a loop inside a loop is fast enough.
  • You must choose between two ideas and want to know which one grows slower.
  • An interviewer asks "what is the time and space complexity?" of your code.
  • A page or script works with 100 items but freezes with 100,000.

Check yourself

Answer each one in your head first, then open it.

If n grows from 1,000 to 2,000, about how many steps does quadraticTime take?

About four times as many: 2000 * 1999 / 2 is 1,999,000, compared with 499,500. Doubling n in an O(n^2) count multiplies it by about 4.

Why is a loop that runs 5n + 100 times still O(n)?

Past n = 100, 5n + 100 is at most 6n, a fixed number times n. Big O keeps only how the count grows, and both double when n doubles.

How many steps does logarithmicTime(1000000) take?

19. Halving a million with Math.floor reaches 1 after 19 steps, because 2 to the 19th power is 524,288 and 2 to the 20th is just over a million.

A loop over items calls items.indexOf(item) each time. What is its time complexity?

O(n^2). indexOf scans the array from the start, which is up to n steps, and it runs once for each of the n items.

Why doesn't linearTime use O(n) space, even though items has n numbers?

Space complexity counts only the memory the code creates. linearTime creates one number, total, whatever the size of items, so its extra space is O(1).

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 2 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Big O has a precise meaning. Saying a step count f(n) is O(g(n)) means: there is some fixed number c and some starting size n0 so that f(n) <= c * g(n) for every n from n0 on. In plain words, past some size, the count never grows faster than g(n) times a fixed amount.

That rule is why fixed numbers and smaller terms can be dropped. A loop that runs 3n + 5 times is O(n): pick c = 4 and n0 = 5, and 3n + 5 <= 4n for every n from 5 on. quadraticTime runs n * (n - 1) / 2 times, which is never more than n * n, so it is O(n^2) with c = 1. The smaller terms still exist, but past n0 they can't change the shape.

The counting rules follow from the same idea. Two loops one after the other add their counts: n + n = 2n, still O(n). A loop inside a loop multiplies: n outer runs times up to n inner runs is O(n^2). A loop that halves n until it reaches 1 runs floor(log₂ n) times, which is why 1,000 takes 9 steps and a million takes 19.

Big O is an upper bound, so it is a promise, not a stopwatch reading. It says how the count grows past some size; it says nothing about which code is faster at n = 5, where fixed costs can win. That is why you check both: Big O to rule out ideas that can't scale, and a real measurement when two ideas are in the same family.

Going deeper

4 more ideas

Why fixed numbers are dropped

Big O answers one question: how does the work grow? A loop that runs 2n times and one that runs n times both double when n doubles, so both are O(n). But n^2 grows much faster: at n = 1,000 it is a million steps, while 2n is only 2,000. Once n is large, the shape of the growth matters far more than any fixed number in front of it.

Common growth rates from fastest to slowest

O(1) (reading an array item or a Map key), O(log n) (binary search), O(n) (one pass over the input), O(n log n) (good sorting such as Array.prototype.sort), O(n^2) (comparing every pair), O(2^n) (trying every subset). A rough rule: a computer does about 100 million simple steps per second, so for n = 100,000, O(n log n) is instant while O(n^2) takes many seconds.

Space complexity counts memory the same way

Space complexity counts the extra memory the code creates, not the input itself. linearTime keeps one number, total, so it uses O(1) extra space. Code that copies the input into a new array or fills a Map with every item uses O(n) space. Recursion uses space too: each call that hasn't finished yet waits on the call stack.

Best, worst, and average cases

Some code takes different numbers of steps for inputs of the same size. Searching an array from the front finds the target in 1 step if it is first (best case) but needs n steps if it is last or missing (worst case). When people say "this is O(n)" without more words, they usually mean the worst case, because that is the one that can freeze a page.

Work it by hand

Every step in a table, with why

Run all four functions on lists of growing size and count how many steps each one takes. Each row doubles n, except the last.

`items` holds `n` numbers for `n` = 3, 6, 12, 24, 48, 96, 1000; `logarithmicTime` gets `n` itself

StepnconstantTimelinearTimequadraticTimelogarithmicTimeWhat happensWhy
131331All four counts are smallWith 3 items there are 3 pairs, and 3 halves once to 1. On tiny inputs the four functions look alike.
2616152n doubledlinearTime doubled from 3 to 6. quadraticTime jumped from 3 to 15 pairs. logarithmicTime needed just one more halving: 6, 3, 1.
312112663Pairs grow 4.4 timesDoubling n again doubles the loop count and multiplies the pair count by 66 / 15 = 4.4.
4241242764Pairs grow 4.2 times276 / 66 is about 4.18. The ratio moves closer to 4 as n grows, because n * (n - 1) / 2 behaves more and more like n * n / 2.
54814811285Pairs grow 4.1 timesThe pattern is now clear: same, plus one, times two, times about four.
69619645606Pairs grow 4.04 timeslogarithmicTime(96) halves 96, 48, 24, 12, 6, 3, 1: six steps for 96 items.
71000110004995009A real-sized inputquadraticTime now counts 499,500 pairs, while logarithmicTime takes 9 halvings: 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1.

At n = 1,000 the counts are 1, 1,000, 499,500, and 9. How each column changes when n doubles (stays the same, doubles, grows about 4 times, adds one) is exactly what O(1), O(n), O(n^2), and O(log n) say.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Big O notationO(1)O(1)Before writing code, to compare ideas. You read the loops and name the growth family; the effort doesn't depend on how big n will get, because you never run anything.
Exact step formulaO(1)O(1)When two ideas are in the same family and the constant matters, write the exact count, like n * (n - 1) / 2 versus n * n, to see which does fewer steps.
Benchmarking with performance.now()O(n)O(1)When you need real milliseconds on real data. You must run the code at the size you care about, so the cost grows with n (shown here for a one-pass loop), and results vary between machines.

Extra memory: O(1) extra space for all four: each keeps one counter (total, pairs, or steps) whatever the size of items. The input itself isn't counted, only what the code creates.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Big O notation and the other approaches, on a scale where each line up is 10 times more steps.
  • Big O notation, Exact step formula O(1)
  • Benchmarking with performance.now() O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Big O notation111
Exact step formula111
Benchmarking with performance.now()101,0001 million

Inputs that need care

5 tricky inputs
An empty list: items = []
constantTime returns undefined, linearTime returns 0, and quadraticTime returns 0. Nothing breaks, but tiny inputs say nothing about growth: Big O only talks about large n.
logarithmicTime(1), logarithmicTime(0), or a negative number
n > 1 is false at once, so the loop never runs and the function returns 0 steps.
A size that isn't a power of two: logarithmicTime(45)
It halves 45, 22, 11, 5, 2, 1: 5 steps, because Math.floor rounds down each time. The count is floor(log₂ n), still O(log n).
Two inputs of different sizes, like a with n items and b with m items
A loop over a followed by a loop over b is O(n + m), and a loop over b inside a loop over a is O(n * m). Don't shorten either to O(n): if m can be much bigger than n, that hides the real cost.
A small n with a big fixed cost per step
For 10 items, an O(n^2) loop doing 45 cheap checks can beat an O(n) loop that makes a network request per item. Big O compares growth, so for small, fixed sizes measure instead.

Variations and follow-ups

Twists interviewers add

Big Omega and Big Theta

Big O is an upper bound: "grows no faster than". Big Omega, written Ω, is a lower bound: "grows at least as fast as". Big Theta, written Θ, means both at once. quadraticTime is Θ(n^2) because it always counts every pair, while a search that can stop early is O(n) but not Θ(n).

Amortized cost

Some operations are usually cheap and rarely expensive, like push on an array that sometimes has to grow. Amortized analysis counts the total cost of a long run of operations and divides by how many there were. That is how push gets an O(1) average even though one push can copy every item.

Several size variables

Many problems have more than one size: the rows and columns of a grid, the nodes V and edges E of a graph, the lengths of two strings. Keep them apart, as in O(rows × cols) or O(V + E), because a graph with few nodes can still have many edges.

Space and the call stack

Space complexity counts the memory the code creates while it runs. Recursion counts too: every call that hasn't returned yet sits on the call stack, so a recursive function that goes n calls deep uses O(n) space even if it never creates an array.

In an interview

Spot it, explain it, answer follow-ups
  • Read the limits first. n <= 20 hints that O(2^n) is allowed, n <= 1000 allows O(n^2), and n up to 10^5 or 10^6 needs O(n log n) or better. About 10^8 simple steps per second is a useful rough budget.
  • When asked for the complexity, name what n is before giving the answer: "n is the length of items, and the nested loop counts every pair, so it's O(n^2) time and O(1) extra space." Interviewers listen for the reason, not just the letters.
  • Count hidden loops out loud. includes, indexOf, slice, spreading an array, and string + in a loop all do work proportional to their size. Saying "this includes is O(n), so inside the loop it makes the whole thing O(n^2)" shows real understanding.
  • Expect the follow-up "can you do better?". The usual answer trades memory for time: a Map or Set turns an O(n) inner search into an O(1) lookup, so O(n^2) becomes O(n) time with O(n) space.

Where frontend code uses it

The same idea in real UI code
  • Calling array.find inside a .map over another large array during render is O(n * m). Building a Map by id first makes each lookup O(1).
  • document.querySelectorAll walks the DOM tree, so running it inside a loop over many elements repeats that walk every time.
  • React's reconciliation (comparing the old and new element trees) is designed to be roughly O(n) in the number of elements, which is one reason keys on list items matter.
  • Filtering a long table on every keystroke is O(n) per key press; for very large tables, teams debounce the input or precompute an index.

Related algorithms