O(n³) — cubic complexity

Things are getting really serious now. Algorithms with O(n³) use three nested loops. This means that as the data grows, the execution time grows cubically.

Example: multiplying two matrices

function matrixMultiplication($matrixA, $matrixB) {
    $rowsA = count($matrixA);
    $colsA = count($matrixA[0]);
    $colsB = count($matrixB[0]);

    $result = [];
    for ($i = 0; $i < $rowsA; $i++) {
        for ($j = 0; $j < $colsB; $j++) {
            $result[$i][$j] = 0;
            for ($k = 0; $k < $colsA; $k++) {
                $result[$i][$j] += $matrixA[$i][$k] * $matrixB[$k][$j];
            }
        }
    }
    return $result;
}

Sounds academic, but it happens more often than you'd think: in calculations, graph building, searching for combinations. Anything that needs to compare triples of data or three-dimensional structures is a candidate for O(n³).

This is a critical point already. If you can avoid code like this — avoid it. You can often find ways to bring it down to O(n²) or even O(n log n).

← Previous: O(n²) — quadratic complexity · Whole series · Next: O(2ⁿ) — exponential complexity →

First published in Ukrainian in the Telegram channel “Created to die” on June 25, 2025.