Project ForgeAlgorithms
Complexity Analysis
GATE 2013
Medium
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
- AΘ(n²)
- BΘ(n²log n)
- Θ(n³)
- DΘ(n³log n)
Explanation
Bellman-Ford performs V−1 relaxation passes, each relaxing every edge once, giving Θ(V·E) overall. A complete graph on n vertices has E = n(n−1)/2 = Θ(n²) edges, so the total time is Θ(n · n²) = Θ(n³).
Source: GATE CS 2013 (2013)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.