The running time and space of Floyd-Warshall on a graph with V vertices and E edges is
AO(V + E) time, O(V) space
BO(V³) time, O(V²) space
CO(E log V) time, O(E) space
DO(V² log V) time, O(V²) space
Answer & Solution
Correct answer: B. O(V³) time, O(V²) space
Floyd-Warshall uses a V × V distance matrix updated by three nested loops, giving O(V³) time and O(V²) space. The space holds the d[i][j] table. Time is independent of E because every (i, j) pair is examined regardless of whether an edge exists. The other options describe BFS or Dijkstra variants.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for