# O(n³) - Cubic Time

> Three nested loops — fine only for n < 100. Gets painful fast.

- **Category**: Big O
- **Subcategory**: complexity
- **Canonical URL**: https://designpattern.fyi/big_o/cubic-time/

---

## Description
Clean, reusable architecture pattern.


## Use Cases
Floyd-Warshall all-pairs shortest path — inherently O(n³) and accepted for small graphs (n < 500 nodes). Naive matrix multiplication for 1000x1000 matrices — 1 billion multiplications vs Strassen's ~333M. Production matrix math uses highly optimized BLAS (LAPACK, cuBLAS).



## Implementation Example

```javascript
// ❌ O(n³) — Naive matrix multiplication (only for learning)
function matMulNaive(A, B) {
  const n = A.length;
  const C = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      for (let k = 0; k < n; k++) { // Triple nested — O(n³)
        C[i][j] += A[i][k] * B[k][j];
      }
    }
  }
  return C;
}
// At n=1000: 10^9 operations. Use a BLAS-backed library in production.

// ❌ O(n³) — 3Sum (naive)
function threeSumNaive(arr, target) {
  const results = [];
  for (let i = 0; i < arr.length; i++)
    for (let j = i+1; j < arr.length; j++)
      for (let k = j+1; k < arr.length; k++) // Triple — O(n³)
        if (arr[i]+arr[j]+arr[k] === target)
          results.push([arr[i],arr[j],arr[k]]);
  return results;
}

// ✅ O(n²) — 3Sum with sort + two pointers
function threeSumFast(arr, target) {
  arr.sort((a,b) => a-b); // O(n log n)
  const results = [];
  for (let i = 0; i < arr.length - 2; i++) {
    let lo = i+1, hi = arr.length-1;
    while (lo < hi) { // Two pointers — O(n) inner loop, O(n²) total
      const s = arr[i]+arr[lo]+arr[hi];
      if (s === target) results.push([arr[i],arr[lo++],arr[hi--]]);
      else s < target ? lo++ : hi--;
    }
  }
  return results;
}

```



## Trade-offs


### Advantages

- Correct and straightforward — three loops are easy to write and verify

- Acceptable for small, bounded n (graph problems with n < 200 nodes)

- Some problems (Floyd-Warshall, naive matrix multiply) are inherently cubic and well-understood

- Useful for establishing a baseline correct solution before optimizing




### Considerations & Drawbacks

- Completely unusable for large n — n=10k means 1 trillion operations

- Even n=1000 can take seconds — most users will notice

- Rarely necessary — almost all O(n³) algorithms have known better alternatives

- Very easy to accidentally write (three innocent-looking nested loops)







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