Big-O and JavaScript's Hidden Costs

Why interviewers ask about complexity

Two programs can return the same answer and behave completely differently as the input grows. Big-O describes the shape of that growth. It does not predict an exact runtime in milliseconds. It answers a more durable question: if the input becomes ten or one thousand times larger, how does the amount of work change?

Let n represent the relevant input size. Count how often the important work can run, then keep the fastest-growing term and ignore constant multipliers:

3n + 20       → O(n)
n² + 4n + 8   → O(n²)
half of n     → O(n)

Dropping constants does not mean constants never matter in real engineering. It means they do not change the long-run growth class. An O(n) algorithm can be slower for tiny inputs and still scale better than O(n²).

The growth classes you need first

Add sequential work; multiply nested work

Two separate full scans take n + n = 2n visits, so they are O(n):

for (const value of values) inspect(value)
for (const value of values) record(value)

If the inner loop runs n times for every one of n outer iterations, the work is n × n, or O(n²):

for (const left of values) {
  for (const right of values) compare(left, right)
}

Different input sizes deserve different names. Comparing every item in a with every item in b is O(a · b), not automatically O(n²). Precision makes your explanation stronger and prevents you from hiding an expensive input behind the wrong variable.

Price the body of the loop

A loop is not automatically O(n). Multiply the number of iterations by the cost of its body. Array.prototype.includes may scan the entire array, so this apparently simple code is O(n²):

for (const value of values) {
  if (otherValues.includes(value)) return true
}

The same warning applies to indexOf, copying with spread, slicing a growing range, front insertion/removal, and many string-building strategies. Method names can hide loops; complexity analysis must look through the method name.

Time and space answer different questions

Time complexity measures work. Auxiliary space measures memory created by the algorithm beyond the input and required output. A Set holding every input value costs O(n) extra space. Five counters cost O(1). A recursive call chain can consume O(n) stack space even when no array or Map is allocated explicitly.

Do not count the input as extra space, and clarify whether an output array is required by the problem. Interviewers often exclude required output from auxiliary-space analysis, but saying your convention removes ambiguity.

Amortized and expected are honest qualifiers

Appending to a dynamic array is amortized O(1). Most appends are constant work; occasionally the engine allocates larger storage and copies existing elements. Spread that occasional cost across many appends and the average per append is constant.

Map and Set operations are usually described as expected O(1). Their performance depends on good hash distribution and controlled load. Week 2 explains that machinery.

Common mistakes

• Reporting only time and forgetting space.
• Calling all nested loops O(n²), even when an inner pointer advances only n times total.
• Treating sort() as free; comparison sorting is generally O(n log n).
• Ignoring a linear helper called inside a linear loop.
• Optimizing constants while leaving a worse growth class untouched.