Most JavaScript developers know what Big O notation is. Fewer actually think about it when writing day-to-day code.
That's a gap worth closing — because the difference between O(1) and O(n) is the difference between a feature that scales and one that silently degrades under load.
This guide connects Big O directly to JavaScript built-ins you use every day.
What Big O Actually Measures#
Big O describes how an algorithm's runtime (or memory usage) grows relative to its input size.
It answers: if I double the input, what happens to the time?
| Notation | Name | Example |
|---|---|---|
| O(1) | Constant | Object property access |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Array.forEach |
| O(n log n) | Linearithmic | Array.sort |
| O(n²) | Quadratic | Nested loops |
The goal is almost always to get as close to O(1) as possible for hot paths.
The Hidden Cost of Array.includes()#
Here's code that looks completely fine:
const allowedRoles = ['admin', 'editor', 'moderator', 'viewer', 'guest'];
function canAccess(role) {
return allowedRoles.includes(role);
}What's the time complexity of canAccess?
O(n) — because Array.includes() performs a linear scan. It checks index 0, then 1, then 2... until it finds a match or exhausts the array.
With 5 items, that's negligible. But this pattern appears everywhere:
// Still O(n) — same problem, different method
const found = users.find(u => u.id === targetId);
const idx = items.indexOf(searchValue);
const has = list.includes(searchValue);
const filtered = products.filter(p => p.category === 'electronics');Every one of these is O(n). Called inside a loop, they become O(n²).
The Fix: Use a Set for Lookups#
// O(n) lookup
const allowedRoles = ['admin', 'editor', 'moderator', 'viewer', 'guest'];
allowedRoles.includes('editor'); // scans the array
// O(1) lookup
const allowedRolesSet = new Set(['admin', 'editor', 'moderator', 'viewer', 'guest']);
allowedRolesSet.has('editor'); // direct hash lookupSet.has() is O(1) — it uses a hash table internally, so the lookup time doesn't grow with the set size.
The conversion itself is O(n), but you do it once. Every subsequent lookup is O(1).
// Real-world pattern: build the Set once, reuse everywhere
const ALLOWED_ROLES = new Set(['admin', 'editor', 'moderator', 'viewer', 'guest']);
function canAccess(role: string): boolean {
return ALLOWED_ROLES.has(role);
}JavaScript Data Structures and Their Complexity#
Array#
| Operation | Complexity | Notes |
|---|---|---|
arr[i] (read by index) | O(1) | Direct memory access |
push() / pop() | O(1) amortized | End of array |
unshift() / shift() | O(n) | Must re-index all elements |
includes() / indexOf() | O(n) | Linear scan |
find() / findIndex() | O(n) | Linear scan |
splice() | O(n) | Shifts elements |
sort() | O(n log n) | Timsort in V8 |
slice() | O(n) | Copies elements |
Key takeaway: arrays are great for ordered data and index-based access, not for membership checks.
Object#
| Operation | Complexity | Notes |
|---|---|---|
obj[key] (read) | O(1) average | Hash lookup |
obj[key] = val (write) | O(1) average | Hash insert |
delete obj[key] | O(1) average | |
key in obj | O(1) average | |
Object.keys() | O(n) | Enumerates all keys |
// O(1) lookups
const userById = {
'user_001': { name: 'Alice', role: 'admin' },
'user_002': { name: 'Bob', role: 'editor' },
};
// Fast — O(1)
const user = userById['user_001'];
const exists = 'user_001' in userById;Set#
| Operation | Complexity |
|---|---|
set.add(val) | O(1) average |
set.has(val) | O(1) average |
set.delete(val) | O(1) average |
| Iteration | O(n) |
Use Set when: you need unique values and frequent membership checks.
Map#
| Operation | Complexity |
|---|---|
map.set(key, val) | O(1) average |
map.get(key) | O(1) average |
map.has(key) | O(1) average |
map.delete(key) | O(1) average |
| Iteration | O(n) |
Use Map over Object when: keys are not strings, you need insertion-order iteration, or you need size without Object.keys().length.
The Nested Loop Trap: O(n²)#
This is the most common performance bug I see in real codebases:
// ❌ O(n²) — finding duplicates the naive way
function hasDuplicates(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j]) return true;
}
}
return false;
}With 1,000 items: ~500,000 comparisons. With 10,000 items: ~50,000,000 comparisons.
// ✅ O(n) — use a Set
function hasDuplicates(arr) {
return arr.length !== new Set(arr).size;
}
// Or iteratively to short-circuit early
function hasDuplicates(arr) {
const seen = new Set();
for (const item of arr) {
if (seen.has(item)) return true;
seen.add(item);
}
return false;
}Hiding O(n²) in React#
This pattern shows up constantly in React components:
// ❌ O(n²) — called on every render, for every item
function ProductList({ products, selectedIds }) {
return products.map(product => (
<ProductCard
key={product.id}
product={product}
isSelected={selectedIds.includes(product.id)} // O(n) inside O(n) loop
/>
));
}If products has 500 items and selectedIds has 200 items, that's 100,000 operations per render.
// ✅ O(n) total — convert once, check in O(1)
function ProductList({ products, selectedIds }) {
const selectedSet = useMemo(() => new Set(selectedIds), [selectedIds]);
return products.map(product => (
<ProductCard
key={product.id}
product={product}
isSelected={selectedSet.has(product.id)} // O(1)
/>
));
}Array.sort() and Comparator Cost#
Array.sort() is O(n log n), which is optimal for comparison-based sorting. But the comparator function runs many times:
// Fine for small arrays
users.sort((a, b) => a.name.localeCompare(b.name));
// For large arrays where you sort repeatedly, pre-compute sort keys
const sorted = users
.map(u => ({ ...u, _sortKey: u.name.toLowerCase() }))
.sort((a, b) => a._sortKey < b._sortKey ? -1 : 1)
.map(({ _sortKey, ...u }) => u);String Operations#
Strings are immutable in JavaScript. Every concatenation creates a new string:
// ❌ O(n²) — each += creates a new string and copies everything
let result = '';
for (const item of items) {
result += item + ', ';
}
// ✅ O(n) — join at the end
const result = items.join(', ');
// ✅ O(n) — array push + join
const parts = [];
for (const item of items) {
parts.push(item);
}
const result = parts.join(', ');Object.keys() / Object.values() Are O(n)#
const config = { host: 'localhost', port: 3000, debug: true };
// Each of these is O(n) — enumerates all keys/values
Object.keys(config).length; // ❌ if you just want to know "is it empty?"
Object.values(config).forEach(...);
// For "is empty" check, O(1):
function isEmpty(obj) {
for (const _ in obj) return false;
return true;
}Practical Lookup Table Pattern#
A common pattern when you repeatedly look up configuration or labels by key:
// ❌ Array of objects — O(n) lookup every time
const STATUS_LIST = [
{ code: 'pending', label: 'Pending Review', color: 'yellow' },
{ code: 'active', label: 'Active', color: 'green' },
{ code: 'closed', label: 'Closed', color: 'gray' },
];
function getStatus(code) {
return STATUS_LIST.find(s => s.code === code); // O(n)
}
// ✅ Object map — O(1) lookup
const STATUS_MAP = {
pending: { label: 'Pending Review', color: 'yellow' },
active: { label: 'Active', color: 'green' },
closed: { label: 'Closed', color: 'gray' },
} as const;
function getStatus(code: keyof typeof STATUS_MAP) {
return STATUS_MAP[code]; // O(1)
}When O(n) Is Fine#
Not every O(n) operation needs to be replaced. Rules of thumb:
Keep O(n) when:
- The array has < 100 items
- The operation runs infrequently (not in a hot render path or tight loop)
- The code clarity benefit outweighs the performance gain
Optimize when:
- The array can grow unbounded with user data
- The operation is inside a loop (potential O(n²))
- It runs on every render or every request
- Profiling shows it as a bottleneck
Quick Reference#
| You're doing | Use | Complexity |
|---|---|---|
| Check if value exists in list | Set.has() | O(1) |
| Look up value by key | Object / Map | O(1) |
| Remove duplicates | new Set(arr) | O(n) |
| Find item by property | Precompute a Map | O(1) per lookup |
| Sorted unique values | Sort once, store sorted Set | O(n log n) once |
| Membership checks in React | useMemo(() => new Set(...)) | O(1) |
The pattern is always the same: if you're checking membership or looking up by key more than once, convert to a Set or Map first.
Working on a React or Node.js application and want a performance review? Get in touch — I work on full-stack projects where this kind of optimization matters at scale.