Why built-ins have a cost
A line like arr.includes(x) looks like one step, but it is a loop that someone else wrote. When you estimate the Big O time of your code, every built-in call counts for the work it does inside. The classic trap is a built-in called inside a loop: a loop that runs n times and calls a method costing O(n) each time takes O(n²), even though the code shows only one loop.
function hasDuplicate(a) {
for (let i = 0; i < a.length; i++) {
if (a.slice(i + 1).includes(a[i])) return true;
}
return false;
}
Both slice (which copies part of the array) and includes (which scans it) cost O(n). They run once per pass of a loop that runs n times, so the function is O(n²). Using a Set fixes it:
function hasDuplicate(a) {
const seen = new Set();
for (const v of a) {
if (seen.has(v)) return true;
seen.add(v);
}
return false;
}
Now each pass does a lookup and an insert, both constant time on average, so the total is O(n). Both versions give true for [1, 2, 3, 1] and false for [1, 2, 3].
Arrays
Below, n is the number of elements in the array. The rule of thumb: an operation that touches only the end of an array is cheap, and one that has to shift or visit many elements is not.
| Operation | Time | Why |
|---|---|---|
arr[i], arr.length | O(1) | Direct access by index |
push, pop | O(1) | Work at the end only (push is O(1) amortized) |
shift, unshift | O(n) | Every other element moves by one position |
splice | O(n) | Elements after the change move |
indexOf, includes, find | O(n) | Scans until it finds a match |
slice, concat, [...arr] | O(n) | Copies elements |
map, filter, forEach, reduce, join, reverse | O(n) | Visit every element once |
sort | O(n log n) | Comparison sort |
Two of these are easy to underestimate. First, shift() removes the first element and moves everything else down, so using an array as a queue with shift in a loop is O(n²) in theory. (Engines can optimize this for some arrays, but you should not rely on that when you reason about complexity.) Second, sort is O(n log n) in comparisons, and calling it inside a loop multiplies that cost.
Also note what sort compares. With no comparator it sorts as strings, so [10, 9, 1].sort() gives [1, 10, 9]. For numbers, pass a comparator: [10, 9, 1].sort((x, y) => x - y) gives [1, 9, 10].
Strings
Strings are immutable, so any operation that changes or builds a string produces a new one and costs time proportional to its length:
s.lengthands[i]areO(1).indexOf,includesandsplitscan the string, so they areO(n). Searching for a text of lengthmin a string of lengthncan take up toO(n * m)in the worst case for a simple search.slice,substring,toUpperCase,trim,replaceandconcatproduce a new string, so thinkO(n)for each.- Building a result with
+=in a loop can look likeO(n²), since each step conceptually copies the string so far. Engines often optimize this, but if you need a guarantee, collect the pieces in an array and calljoin("")once at the end, which isO(n).
Maps, sets and objects
Map and Set are built on hash tables. get, set, has, add and delete are O(1) on average. Reading map.size is O(1), and iterating over all entries is O(n). The word "average" matters: in the worst case a hash table can degrade, but for the problems in this course you can treat these operations as constant time.
Plain objects used as dictionaries behave similarly: obj[key], assigning to it, key in obj and delete obj[key] are constant time on average. Object.keys(obj), Object.values(obj) and Object.entries(obj) build an array of all the keys, values or entries, so they cost O(n) and should not be called inside a loop that runs for every key.
Hidden loops
These calls look like single operations and are not:
Math.max(...arr)spreads the array into arguments and then looks at each one:O(n). Very large arrays can also exceed the engine's limit on the number of arguments.[...arr]andArray.from(arr)copy the array:O(n).JSON.stringify(obj)andJSON.parse(text)are proportional to the size of the data.
How to use this when you write code
- Count the loops. Look at every loop, and at every built-in call inside it.
- Multiply a call's cost by how often it runs. An
O(n)call inside ann-pass loop isO(n²). - Replace repeated scans with lookups. If you keep asking "have I seen this value?", store values in a
Setor aMapinstead of searching an array. - Keep the dominant term. Work that is
O(n)plusO(n log n)for a sort isO(n log n)overall.
Key takeaways
- Built-in methods hide loops:
includes,indexOf,slice,concat,shiftandspliceare allO(n). push,popand index access areO(1).sortisO(n log n), and without a comparator it sorts as strings.Map,Setand object lookups areO(1)on average, which makes them the standard tool for removing a nested scan.- When a built-in sits inside a loop, multiply the two costs.
