When O(n²) Becomes a Problem
You'll learn to recognize when nested loops create performance bottlenecks that scale poorly with data growth.
The Scaling Reality
O(n²) complexity means your algorithm's running time grows with the square of your input size. With 10 items, that's 100 operations. With 100 items, that's 10,000 operations. With 1,000 items? A million operations. This exponential growth turns fast code into frozen browsers.
The Nested Loop Culprit
The most common O(n²) pattern is nested loops where each loop iterates over the same dataset:
function findDuplicates(arr) {
const duplicates = [];
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] === arr[j]) {
duplicates.push(arr[i]);
}
}
}
return duplicates;
}
// Small dataset: fine
findDuplicates([1, 2, 3, 2]); // Fast
// Large dataset: disaster
const bigArray = new Array(10000).fill(0).map((_, i) => i);
findDuplicates(bigArray); // Freezes!
When It Becomes a Problem
O(n²) is acceptable for:
- Small, fixed-size datasets (< 100 items)
- Operations that run rarely
- Prototyping phase
It becomes problematic when:
- Dataset size is user-dependent or unbounded
- The operation runs frequently (on every render, keystroke, etc.)
- Response time matters (UI interactions, API responses)
Think of it like sorting a deck of cards by comparing every card to every other card — fine for a small deck, absurd for a whole warehouse of decks.
Key Takeaway: Nested loops over the same dataset create O(n²) complexity that scales poorly; always consider whether your data might grow beyond a few hundred items before shipping such code.