Back to Catalog
Big O
Avoid in Prod
O(n³) - Cubic Time
Three nested loops — fine only for n < 100. Gets painful fast.
Intent & Description
Real-world Use Case
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).
Source
📌 TL;DR
O(n³) = three nested loops. Usable only for n < ~200. The 3Sum problem drops to O(n²) with sort+two-pointer. Matrix math uses BLAS. If you have O(n³), there is almost certainly a better way.
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
Disadvantages
- 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)
Implementation Example
// ❌ 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;
}