Floyd-Warshall algorithm in Data Structures Theory - Time & Space Complexity

Time Complexity: Floyd-Warshall algorithm

O(n³)

Understanding Time Complexity

We want to understand how the Floyd-Warshall algorithm's running time changes as the graph size grows.

Specifically, how does the number of steps increase when we add more nodes?

Scenario Under Consideration

Analyze the time complexity of the Floyd-Warshall algorithm below.

for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    

This code updates the shortest paths between all pairs of nodes by considering each node as an intermediate step.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The triple nested loops that update distances.
• How many times: Each loop runs n times, so the inner update runs n x n x n = n³ times.

How Execution Grows With Input

As the number of nodes n grows, the steps increase by roughly the cube of n.

Input Size (n)	Approx. Operations
10	1,000
100	1,000,000
1000	1,000,000,000

Pattern observation: If you double the number of nodes, the work grows eight times (2³ = 8).

Final Time Complexity

Time Complexity: O(n³)

This means the time needed grows very quickly as the graph gets bigger, roughly proportional to the cube of the number of nodes.

Common Mistake

[X] Wrong: "Since there are three loops, the algorithm must be O(n) because loops run one after another."

[OK] Correct: The loops are nested inside each other, so the total steps multiply, not add. This makes the time grow much faster than just n.

Interview Connect

Understanding Floyd-Warshall's time complexity helps you explain why it works well for small graphs but can be slow for large ones, showing your grasp of algorithm efficiency.

Self-Check

"What if we replaced the triple nested loops with a recursive approach? How might that affect the time complexity?"