Big‑O, Allocation, and Measured JavaScript Performance

An algorithm can have a better growth rate and still take longer on the input in front of you. That isn't a contradiction. The growth rate describes how work changes as the problem gets larger; the stopwatch includes the work you actually asked the runtime to do.
I find this distinction particularly useful in JavaScript, where replacing a short scan with a collection can add allocation, construction, and later garbage collection. The new structure may be exactly what a busy application needs. Building it for three lookups might be an expensive way of feeling organised.
I'll use a small membership problem to separate those decisions. We have an array of numbers and a batch of queries, and want to count how many queries occur in the array. Repeated queries count separately. The useful question is when to scan, when to build an index, and what a measurement of either approach actually establishes.
Name the Input Before Naming the Complexity
Let n be the number of values and q the number of queries. Scanning the array for every query takes O(nq) time in the worst case. If q grows in proportion to n, that becomes O(n²). If q stays at 32, it is linear in n. Describing both workloads as simply "quadratic" loses the decision we need to make.
Big‑O is an asymptotic upper bound. It doesn't say "this takes ten milliseconds", and it isn't inherently a worst‑case notation: we must specify which cost we are bounding. We can discuss a worst‑case bound, an average over a stated input distribution, or a bound on a sequence of operations.
A scan can also stop early. A missing value requires examining the whole array; a value in its first position needs only the first comparison. Both belong to the same implementation. A benchmark full of first‑position hits answers a very different question from one full of misses.
The cost of an elementary operation matters too. This experiment uses ordinary numbers. Comparing long strings, deriving a key from an object, or running a custom comparator introduces work that a simple "one operation" model can conceal. Define the domain before generalising the result.
My merge‑sort walkthrough makes the same distinction about storage: mutating the caller's array doesn't mean an implementation uses constant auxiliary space. Names are convenient; the accounting still needs doing.
Three Implementations, Two Different Timing Boundaries
Here are typed versions of the complete functions used in my experiment. The downloadable JavaScript uses the same implementation with the type annotations removed. The first searches directly, the second queries a supplied Set, and the third constructs that Set before querying it.
export const countByScanning = (values: readonly number[], queries: readonly number[]): number => {
let matches = 0;
for (const query of queries) {
if (values.includes(query)) matches += 1;
}
return matches;
};
export const countInIndex = (index: ReadonlySet<number>, queries: readonly number[]): number => {
let matches = 0;
for (const query of queries) {
if (index.has(query)) matches += 1;
}
return matches;
};
export const countWithNewIndex = (values: readonly number[], queries: readonly number[]): number =>
countInIndex(new Set(values), queries);These functions preserve query multiplicity: querying seven twice adds two matches when seven exists. They don't count how many copies of seven occur in the values array. All three leave their inputs alone.
For numeric membership, includes and Set membership agree on NaN and treat positive and negative zero as equal. That follows from the comparison rules in the array specification and the Set specification. Replacing includes with indexOf would change the NaN case. A faster answer to a slightly different question is not a successful optimisation.
For the usual hash‑table cost model, Set construction takes expected O(n) time and each membership query takes expected O(1). Under that assumption, building and querying takes expected O(n + q), whilst querying an existing index takes expected O(q). ECMAScript itself requires average sublinear access, rather than promising a particular hash table or worst‑case constant‑time lookup. Keep that qualification attached to the model.
| Approach | Work counted for one query batch | Additional retained structure |
|---|---|---|
| Repeated scan | Up to n comparisons for each of q queries | No index |
| Build and query | Index construction plus q lookups | Up to n distinct values for this call |
| Query existing index | q lookups; construction happened earlier | An index kept across calls |
The final row is a legitimate measurement of an existing index. It is not a fair price for introducing that index into a request that previously had none. If the values change, the index must be maintained or replaced. Reusing a stale Set is an excellent way to make incorrect code look quick.
Amortised Doesn't Mean Every Operation is Cheap
Average‑case and amortised analysis answer different questions. An average‑case argument needs assumptions about inputs, hashing, or both. An amortised argument adds the cost over a sequence of operations, including the expensive ones, and spreads that cost across the sequence. It needn't assume random inputs.
Consider an idealised dynamic array that doubles its capacity when full. Most appends write one element. An append that triggers growth also copies the existing elements. Across n appends, the copied capacities form a geometric sum smaller than a constant multiple of n, giving constant amortised append cost despite individual linear‑cost growth operations.
That's a model explaining a common implementation strategy, not an ECMAScript guarantee about every push call. JavaScript arrays can have different representations, and unusual property behaviour changes the problem further. V8's explanation of element kinds is useful background on why arrays with different contents needn't behave identically.
The practical consequence is latency. A low average cost doesn't rule out a slow individual request. If one request triggers rebuilding a large index, that request pays the bill even when the next thousand requests benefit. For a latency‑sensitive path, I want the distribution of request times as well as an amortised argument.
There is also a simpler accounting question for our index. For k batches over unchanged data, compare k scans with one construction plus k indexed batches. Whether reuse pays depends on k, the query positions, the data size, and the cost of keeping the index correct. No complexity label supplies a universal break‑even count.
Count Allocation Separately from Retained Memory
The build‑and‑query version creates a fresh Set on every call. That means repeated construction work and temporary storage, even though the Set needn't remain reachable after the call. The reused version retains one index for longer. These are different memory policies.
Peak live memory, total allocation over time, and retained memory after a workload are distinct quantities. An implementation can have a modest live set whilst allocating repeatedly. Another can allocate infrequently but retain a large index for the life of the application.
A loop that copies an ever‑growing accumulator illustrates the difference. Copying lengths one, two, three, and so on produces O(n²) cumulative element‑copying work, even if old copies soon become unreachable. Looking only at the final array misses that work. Conversely, one temporary array in a readable transformation is not automatically a performance problem worth rewriting.
I wouldn't infer allocated bytes from a before‑and‑after heapUsed subtraction. Collection can run between those samples, and temporary allocations can disappear from the final measurement. Nor would I infer a garbage‑collection pause from one slow timing. Node's garbage‑collection tracing guide describes evidence we can collect when that is the question.
This lab measures elapsed runtime. It doesn't measure allocation volume or attribute individual delays to the collector. The source tells us which variant creates a Set; the timings alone don't tell us how much of a difference comes from allocation, hashing, iteration, or collection. My memory‑management article covers retained references and allocation investigations in more detail.
Check the Answer Before Starting the Clock
The accompanying tests compare the implementations with a separate, straightforward reference. They cover empty arrays, duplicate values, repeated queries, missing values, NaN, signed zero, and infinities. Small exhaustive arrays exercise combinations that a single large random input would easily miss.
I also test the index lifecycle explicitly: create an index, change the original array, and observe that the old index still describes its earlier contents. This isn't a bug in Set. It's a contract the caller needs to understand.
Before timing, the harness verifies all generated cases against the reference. During timing, it accumulates each returned count into a checksum, then checks that checksum outside the timed region. This gives the result an observable use and catches accidental changes to the answer. It doesn't prove that the engine performs every source‑level operation literally; optimisation is part of what we're measuring.
Correctness and timing remain separate commands. A passing test suite doesn't establish a speed advantage, and noisy timings shouldn't make a correctness test fail. My algorithm‑testing guide develops the oracle and invariant side of that workflow.
Choose Inputs That Can Disagree with You
The lab uses arrays of 64, 1,024, and 16,384 numbers, with 32 queries per batch. The unique‑value arrays use a fixed seeded shuffle. A second family repeats just eight values. These are synthetic inputs, designed to expose differences rather than represent a production traffic sample.
For each size, there are four cases:
- Every query finds the first value in a shuffled unique array.
- Queries find values spread across that array.
- Every query misses the unique array.
- An array containing eight distinct values receives an even mixture of hits and misses.
The first case deliberately favours scanning. The missing‑value cases make it traverse the whole array, whilst duplicates change how much distinct data an index retains. I want that disagreement visible. A benchmark that politely agrees with its author hasn't been given much to do.
Fixed inputs make comparisons reproducible, but this remains a narrow workload. There are no strings, sparse arrays, accessor properties, concurrent requests, or browser rendering. Changing the query count is a useful next experiment because it changes how much work can repay index construction. Keep the original observations and save new results separately.
Be Explicit About What the Timer Includes
The harness uses Node's performance.now() and times repeated complete query batches. It divides elapsed time by the number of repetitions. Input creation, correctness checks, warm‑up, calibration, and writing the results file happen outside each recorded interval.
Set construction stays inside the timed operation for build‑and‑query. For query‑existing‑index, construction happens before timing and is explicitly excluded. Function calls, loop overhead, and checksum addition remain included for every variant.
Each variant receives 64 warm‑up calls, followed by pilot calibration towards a 12‑millisecond interval, capped at 4,096 repetitions. Nine recorded rounds rotate which variant runs first. Fast cases can still produce short intervals at that cap, so the smaller numbers deserve particular caution. The raw files preserve each sample and its repetition count.
A fixed warm‑up is not proof that the runtime has reached a stable optimised state. V8 uses just‑in‑time compilation in its normal configuration, as its JIT‑less mode explanation makes clear. Compilation, changed assumptions, garbage collection, operating‑system scheduling, and other work on the machine can affect observations.
I repeat the full experiment in three fresh processes. That exposes some run‑to‑run variation, but doesn't isolate the processor or remove every ordering effect. Cases run in a fixed order, and rotating variants can't undo all shared process history. This is a small inspectable experiment, not a laboratory certificate.
Read the Observations at Their Actual Scale
The retained observations were collected on 19 November 2026 using Node v22.23.5, V8 12.4.254.21‑node.57, and an Apple M2 running macOS on arm64. These are current measurements accompanying the article, not a claim about an earlier runtime or a historical experiment.
For 16,384 values and 32 queries, the table shows the range of the three process medians, in microseconds per complete query batch. Each process median comes from its nine samples. I have rounded the display; the download retains the raw milliseconds.
| Query distribution | Scan | Build and query | Query existing index |
|---|---|---|---|
| First‑position hits | 0.16 to 0.17 | 557.82 to 659.82 | 0.16 to 0.16 |
| Spread hits | 53.18 to 61.37 | 531.10 to 645.70 | 0.16 to 0.18 |
| All misses | 102.66 to 116.02 | 497.97 to 576.69 | 0.16 to 0.20 |
| Eight distinct values, mixed queries | 51.11 to 58.24 | 83.18 to 97.43 | 0.16 to 0.17 |
Construction cost dominated build‑and‑query in these cases. The prebuilt index answered quickly, but its construction and retained storage were outside that timed operation. For first‑position hits, the scan and existing‑index measurements were both tiny; I wouldn't turn their small separation into a general recommendation.
The all‑miss scan examined every value for each query, yet rebuilding the Set was slower here. That result is compatible with the growth model: q is fixed at 32, the constants differ, and the index hasn't been reused. It doesn't establish that scanning wins for larger query batches or repeated application requests.
These ranges describe observed variation, not confidence intervals. Nine averaged samples don't establish a request‑level 99th percentile, and three processes don't describe every machine. If a small difference would determine an expensive rewrite, I would collect more representative evidence before choosing it.
Use the Result to Make a Decision
Use my JavaScript algorithm measurement lab to run the correctness tests, inspect the recorded environment, and repeat the measurements. It has no dependencies to install. The README identifies the included raw observations and explains how to preserve them when running a new experiment.
I start with the simplest correct implementation that meets the required input scale. Then I use the growth argument to identify where it will struggle, and a measurement of the real workload to decide whether a more complicated representation earns its keep.
If scans dominate a hot path and data survives many query batches, an index is worth investigating. If inputs are small or matches occur near the beginning, constructing one may add work. If request latency is the problem, measure requests rather than treating a loop's average as a latency percentile.
Big‑O helps me predict which work will grow. Allocation analysis tells me what storage and lifetime choices accompany it. Measurement tells me what happened under a stated set of conditions. I need all three before I can reasonably call the code faster.