liveBook · Manning

Cubic complexity

As explained in Algorithms Every Programmer Should Know

A time complexity that grows proportionally to the cube of the input size.

Cubic complexity means the work grows on the scale of the input size cubed. In Floyd–Warshall, three nested loops check every combination of intermediate, starting, and destination vertices, giving O(V³) time for V vertices. The algorithm stores a V × V distance matrix, using O(V²) space. section 9.1

Counting the loops

For a graph with four vertices, the algorithm tests each vertex as a bridge for every start-and-destination pair. It proceeds through bridge vertices in phases, updating the distance matrix as it finds cheaper routes. section 9.1

Listing 9.1 Pseudocode for Floyd Warshall algorithm
Define infinity as a value larger than any possible path distance.
Initialize a 2D array distance_matrix matching the dimensions of the input graph.
 
For each row i and column j in the graph:
    If there is a direct edge from i to j, distance_matrix[i][j] = edge_weight
    If i equals j, distance_matrix[i][j] = 0
    Else, distance_matrix[i][j] = infinity
 
For every vertex k (acting as the intermediate bridge):
    For every vertex i (acting as the start node):
        For every vertex j (acting as the destination node):
            If distance_matrix[i][k] + distance_matrix[k][j] < distance_matrix[i][j]:
                Update distance_matrix[i][j] to the new cheaper sum
 
Return distance_matrix
 

Follow the three nested loops that account for the algorithm’s cubic running time. section 9.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Derives O(V³) from three nested loops and contrasts it with O(V²) matrix storage.
Examples
Traces bridge-vertex phases that update a four-vertex graph’s distance matrix.
What you can do after
Evaluate algorithm cost by identifying three nested loops over graph vertices.
How it connects
Connects cubic complexity to Floyd–Warshall, all-pairs shortest paths, and nested loops.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.