Skip to content

Big-O and the real cost of JS built-ins

Count what the loop body does per item; a scan or a shift inside a loop multiplies, a Set lookup does not.

Predict first

Before you read: predict

ExamHall checks each submitted attempt ID against the list of registered IDs. None of the 2,000 submitted IDs is registered:

By the spec algorithm, how many elements of registered do the 2,000 includes calls read in total?

Code for this question
const registered = Array.from({ length: 2000 }, (_, i) => 'R-' + i);const submitted = Array.from({ length: 2000 }, (_, i) => 'S-' + i);let unknown = 0;for (const id of submitted) {  if (!registered.includes(id)) unknown++;}export { registered, unknown };
Pick one

The 30-second version

Big-O says how work grows with input size. A built-in call is not one step: includes, indexOf and find read element by element; shift and splice move elements to close the gap. Inside a loop each is a hidden inner loop: n × m. Build a Set once and look up: the loop turns linear.

Count what the loop body does per item; a scan or a shift inside a loop multiplies, a Set lookup does not.

How it works

Step 1 of 10

Big-O is growth, not speed. Count the steps as a function of input size n, and ask what happens when n doubles.

Analogy: A snooker hall's front desk on a league night (cue sports)

On league night the desk checks members in, hands out cue lockers and keeps a waiting list for tables on a chalkboard.

At the snooker hall In the code
reading down the paper booking sheet from the top for each arriving member includes in a loop (steps 2, 4)
a member not on the sheet costs the whole sheet; one near the top, a line or two a miss reads everything (step 3)
labelling the cue lockers, one per member, by one walk along the membership list building the Set once (step 8)
each member then goes straight to a numbered locker one lookup per item (step 7)
when the first pair gets a table, every name below is rubbed out and written one line up shift (step 5)
a pair leaving from the middle rewrites every name below them splice (step 6)

In real terms: cost is the number of elements a call touches; a scan touches up to all of them, a hash lookup touches a bounded number on average.

Breaks down when: the desk can glance down a short sheet; code reads one slot at a time. And two lockers never share a number, while two keys can land in one hash bucket: that is why the spec says "on average".

Contrasting case: a pub with one table and a two-name queue. Reading the list costs nothing worth fixing: Big-O matters as n grows.

Examples, run for real

4.1 ExamHall EXH-4210: 40,000 IDs checked with includes

ExamHall checked submitted attempt IDs against an array of registered IDs with includes in a loop. At exam size, 40,000 against 40,000, the check crawled (EXH-4210). Counted at three smaller sizes:

4.1 EXH-4210 includes, 1,250 IDs against 1,250: 1,562,500 element reads
4.1 EXH-4210 includes, 2,500 IDs against 2,500: 6,250,000 element reads
4.1 EXH-4210 includes, 5,000 IDs against 5,000: 25,000,000 element reads
4.1 each doubling multiplies the reads by 4; reads = size² at all three sizes, so 40,000 against 40,000 is 1,600,000,000 (arithmetic, not run)
4.1 MR !4510 new Set(registered) once, then has(): 160,000 counted operations in all at 40,000

Every submitted ID is a miss, so each call reads the whole array (step 3), and doubling both lists quadruples the work (step 4). MR !4510 builds the Set once (step 8) and looks each ID up (step 7): 160,000 counted operations in all, where includes needed 1.6 billion reads.

4.2 Ticketing: a waiting list drained with shift()

A box office serves its waiting list from the front:

while (waiting.length > 0) served.push(waiting.shift());
4.2 shift() drains 1,000 fans: 499,500 element writes on the waiting list
4.2 shift() drains 2,000 fans: 1,999,000 element writes on the waiting list
4.2 doubling the list multiplies the writes by 4.00

Each shift copies every remaining fan one place down (step 5), and doubling the list quadruples the writes. What to use instead is dsa-stack-queue's lane.

Try it

Answer first, then check. Nothing is saved.

Question 1 of 6

A support chat gives each new conversation to the agent at the front of its rota, then moves that agent to the back. The rota holds 500 agents, and 200 conversations arrive:

By the spec algorithm, how many element writes do the 200 shift calls and the 200 push calls make on rota in total?

Code for this question
const rota = Array.from({ length: 500 }, (_, i) => 'agent-' + i);const assigned = [];for (let c = 0; c < 200; c++) {  const agent = rota.shift();  assigned.push(agent);  rota.push(agent);}export { rota, assigned };
Pick one

Question 2 of 6

A gate scanner drops repeat scans of the same ticket. Someone added a Set, yet the gate still slows down as the queue grows:

The harness counts every array element read or written and every Set call, on 1,000 and then 2,000 distinct ticket IDs.

Which one change keeps the output and makes the count at most double when the IDs double?

Code for this question
export function dedupe(ids) {  const out = [];  const seen = new Set();  for (const id of ids) {    if (!out.includes(id)) { seen.add(id); out.push(id); }  }  return out;}
Pick one

Question 3 of 6

A ledger matches each incoming payment to its open invoice. Today 160 payments arrive and 1,250 invoices are open; none of the payments matches an invoice:

By the spec algorithm, how many elements of invoices do the find calls read?

Code for this question
const invoices = Array.from({ length: 1250 }, (_, i) => ({ ref: 'INV-' + i }));const refs = Array.from({ length: 160 }, (_, i) => 'PAY-' + i);const matched = [];for (const ref of refs) {  const inv = invoices.find((x) => x.ref === ref);  if (inv) matched.push(inv);}export { invoices };
Pick one

Question 4 of 6

A video app removes the skipped tracks from a 1,000-track playlist, walking from the end; every even-numbered track was skipped:

By the spec algorithm, how many element writes do the 500 splice calls make on tracks?

Code for this question
const tracks = Array.from({ length: 1000 }, (_, i) => ({ id: i, skipped: i % 2 === 0 }));for (let i = tracks.length - 1; i >= 0; i--) {  if (tracks[i].skipped) tracks.splice(i, 1);}export { tracks };
Pick one

Question 5 of 6

ExamHall's nightly job checks 10,000 late submissions against 25,000 registered IDs; none is registered. The harness counts every array element read and every Set call:

How many counted operations does the job make, from new Set to the end of the loop?

Code for this question
const registered = Array.from({ length: 25000 }, (_, i) => 'R-' + i);const late = Array.from({ length: 10000 }, (_, i) => 'L-' + i);const known = new Set(registered);let unknown = 0;for (const id of late) if (!known.has(id)) unknown++;export { unknown };
Pick one

Question 6 of 6

A chat app resolves the @mentions in a busy channel. There are 800 members, and the 320 mentions name members 1, 3, 5, … 639, each of whom is in the list:

By the spec algorithm, how many elements of members do the 320 indexOf calls read in total?

Code for this question
const members = Array.from({ length: 800 }, (_, i) => 'user' + i);const mentions = Array.from({ length: 320 }, (_, i) => 'user' + (i * 2 + 1));let resolved = 0;for (const name of mentions) if (members.indexOf(name) !== -1) resolved++;export { members, resolved };
Pick one

Go deeper

Pro tips
  1. Scan the loop body for includes, indexOf, find, shift or splice. When: reviewing any loop over a list that can grow (step 9). Each is O(n) per call; a Set or Map built once usually removes it. Verify (RAN, tips.mjs): (The curriculum row's tip, [SELF].)
    tip 1 the same membership check at 3,000 IDs: includes 9,000,000 element reads · a Set built once 12,000 counted operations
  2. Measure growth by counting, not by timing: run the check at n and 2n and compare the counts. When: you need evidence for a reviewer that a loop is quadratic (step 1). A ratio near 4 is quadratic, near 2 is linear. Verify (RAN, tips.mjs):
    tip 2 includes check at 1,500 and 3,000: ×4.00 · Set check at 1,500 and 3,000: ×2.00
Source

Vendor pages change, so their claims are labelled as of 2026-10-14; every count this lesson grades is executed on Node 24. The curriculum row's first source, Cormen et al., is a book and keys nothing.

Related lessons

Checked against the tools and docs as of 2026-10-15.