# O(n²) - Quadratic Time

> Two nested loops over the same data — fine for n<1000, catastrophic at scale.

- **Category**: Big O
- **Subcategory**: Avoid in Prod
- **Canonical URL**: https://designpattern.fyi/patterns/quadratic-time/

---

## Description
Clean, reusable architecture pattern.


## Use Cases
Naive duplicate check: for each element, scan the rest of the array — O(n²). The fix: insert everything into a Set in one pass — O(n). Same result, 1000x faster at n=1000.



## Implementation Example

```javascript
// ❌ O(n²) — Naive duplicate check (avoid for large arrays)
function hasDuplicatesSlow(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) { // Inner loop — O(n²)
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

// ✅ O(n) — Hash set approach (same result, linear time)
function hasDuplicatesFast(arr) {
  const seen = new Set();
  for (const x of arr) {
    if (seen.has(x)) return true; // O(1) lookup
    seen.add(x);
  }
  return false;
}

// ❌ O(n²) — Bubble sort (never use in production)
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) { // Nested — O(n²)
      if (arr[j] > arr[j + 1]) [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
    }
  }
  return arr;
}

// ✅ O(n log n) — Use the built-in (Timsort under the hood)
arr.sort((a, b) => a - b);

```



## Trade-offs


### Advantages

- Simple to write — nested loops are intuitive and readable

- Correct by construction — no clever tricks to get wrong

- Perfectly fine for n < ~1000 items where performance is irrelevant

- Useful for learning — understanding why O(n²) is slow teaches algorithmic thinking




### Considerations & Drawbacks

- Degrades catastrophically with scale — n=100k means 10 billion operations

- Almost always has an O(n log n) or O(n) alternative that is worth using

- The most common cause of production performance incidents on growing datasets

- Easy to miss in code review — the inner loop may be hidden inside a called function







---
**Reference**: [Original Source](https://www.bigocheatsheet.com)