Cubic (O(n³))

At a glance: The amount of work or memory cells grows with the cube of input size.

Jump to: Time complexity · Space complexity · Try it yourself

Understand the growth

When a process considers every ordered triple of objects, it chooses an index for the first, second and third object. There are n possibilities at each choice, giving n × n × n combinations.

Doubling n multiplies a cubic count by eight, because (2n)³ = 8n³. Halving n reduces it by a factor of eight. Cubic growth is slower than exponential growth asymptotically, but it can still make moderately large inputs too expensive.

Three independent dimensions

A triple loop that considers i, j and k over the same n-element set visits n³ ordered triples. The third index is not merely decorative: it multiplies every pair (i,j) by another n possibilities. Doubling the input multiplies the count by eight, while increasing it tenfold multiplies the count by one thousand.

Cubic growth also arises in dynamic programs indexed by three independent variables. For example, some interval algorithms try every possible split point for every interval; the number of interval/split combinations can be Θ(n³). Floyd-Warshall’s classic all-pairs shortest-path algorithm uses a triple loop over vertices and performs Θ(v³) relaxations, where v is vertex count.

A nested-loop shape is only evidence, not proof. If k ranges over a constant number of choices, or the inner loop exits frequently, the full count may be lower. If the innermost operation takes nonconstant time, the complete algorithm can be worse than cubic.

Worked example

At n = 10 there are 1,000 triples. At n = 20 there are 8,000, and at n = 100 there are one million. A byte cube at n = 1,000 already requires about one billion bytes before overhead.

Count ordered triples

For five indices there are 5 × 5 × 5 = 125 ordered triples. For ten there are 1,000, and for twenty there are 8,000. A program that spends a microsecond on each triple would use roughly eight milliseconds for 20 items under that simplified model, but such arithmetic is only an illustration: runtime overhead and data access make the true timing hardware-dependent.

In a graph application, 200 vertices produce eight million (i,j,k) combinations. A dense v × v distance matrix has only 40,000 entries, which demonstrates that Θ(v³) work can coexist with Θ(v²) storage.

Time complexity

Representative time example: Enumerating all triples.

Three fully nested loops that independently range from zero to n - 1 execute their body n³ times. This appears in simple triple enumeration and naive formulations of some matrix operations. However, the cost of Work(i, j, k) must also be included: if the body performs a nonconstant operation, the total can exceed O(n³). Conversely, modern matrix multiplication algorithms can achieve different complexity bounds, so a triple-loop example should not be presented as a universal lower bound.

Account for every loop range

Three loops independently visiting indices [0, n) execute the inner Work(i,j,k) exactly n³ times. If Work is O(1), the time is Θ(n³). If Work scans n additional elements, the total becomes Θ(n⁴); if it always runs in bounded time, constant factors do not change the cubic class.

Floyd-Warshall uses one iteration per possible intermediate vertex k, with an n × n update for each k: this is another way to see Θ(n³). Each update is constant work under fixed-width arithmetic. For real graphs, specify vertex count v rather than n if the latter might be mistaken for the number of edges. Performance can become prohibitive even for moderate v, so candidate pruning and alternative algorithms matter.

C#

C# | Cubic.cs

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        for (int k = 0; k < n; k++)
            Work(i, j, k);

C++

C++ | cubic.cpp

for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
        for (int k = 0; k < n; ++k)
            work(i, j, k);

Analysis: Three independent n-sized nested loops give O(n³) time if Work is constant time.

The C++ version illustrates the same operation. The container, compiler and any functions called by the example still matter when analyzing a complete program.

Space complexity

Representative memory example: A 3-D n × n × n array.

A genuine three-dimensional n × n × n array has n³ elements. If each element is a byte, the raw payload is approximately n³ bytes, ignoring metadata and alignment. This is different from the three nested loops, which typically need only three scalar counters. If the input is already a cube, including it in total memory is different from counting a newly allocated output cube as auxiliary or output storage.

A cube of cells versus a cube of operations

A true n × n × n array stores Θ(n³) values, which can exhaust memory quickly. With one byte per cell, n = 1,000 requires about one billion data bytes before array metadata. With four-byte integers, the payload is roughly four billion bytes. Allocation limits and overhead make practical limits stricter than the asymptotic formula suggests.

But the triple-loop example itself can use only Θ(1) auxiliary space for its three indices. Floyd-Warshall typically stores an n × n distance matrix, which is Θ(n²) space, despite its Θ(n³) time. Streaming or recomputing triple relationships can likewise avoid materializing the full cube. Decide whether results must remain available for arbitrary later lookup before choosing the data structure.

C#

C# | Cubic.cs

byte[,,] cube = new byte[n, n, n];

C++

C++ | cubic.cpp

#include <vector>
#include <cstdint>

std::vector<std::uint8_t> cube(static_cast<std::size_t>(n) * n * n);

Analysis: A three-dimensional n × n × n allocation uses O(n³) auxiliary space; the triple loop above still uses only O(1) extra loop-variable space.

The stated bound describes stored elements and active call frames. Actual byte counts also depend on runtime, allocator and element representation.

Recognize cubic bottlenecks early

Look for three dimensions that vary with the same input size, and ask if all combinations must be inspected. If one dimension is actually fixed (for example a three-channel RGB value), multiplying by that constant does not create cubic growth. If a triple loop stores just one aggregate statistic, its memory may remain constant.

Cubic algorithms are sometimes appropriate for small dense instances, especially when they are simple and provide useful guarantees. For a larger problem, consider whether a sparse graph structure, a specialized shortest-path method, caching, or eliminating a redundant dimension can reduce work. A change in data representation can be as important as a faster innermost instruction.

Practical example: paths between every pair of locations

A map system may need the shortest travel cost between every pair of v locations. Floyd-Warshall considers each location as a possible intermediate stop and updates every origin-destination pair. This produces Θ(v³) updates under the usual constant-time arithmetic model, while storing the distance matrix takes Θ(v²) space. The data structure is two-dimensional, even though the computation has three nested loops.

For a small, dense network, this straightforward algorithm can be a useful choice. For a large sparse road graph where you only need a route from one start, running a more specialized shortest-path algorithm may be preferable. The correct decision depends on which queries the application actually needs, not just the number of loops.

Common mistake

Watch out: Do not infer O(n³) memory from three nested loops. The number of simultaneous variables is usually constant unless the program stores the triples or allocates a three-dimensional structure.

Try it yourself

Calculate how many loop-body calls occur for n = 5, 10, and 20. Then estimate the size of a byte[,,] with the same dimensions.

1. Define exactly what n represents.
2. Count the key operation in the best and worst case where relevant.
3. Count the maximum simultaneously live memory.
4. Check your prediction in the Big O explorer.

Continue learning

Big O overview · Time complexity · Space complexity · Compare classes