Multiple choice

What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?

  1. $\Theta$(n2)
  2. $\Theta$(n2 logn)
  3. $\Theta$(n3)
  4. $\Theta$(n3 logn)
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

Bellman – Ford time complexity: $\Theta$ (|V|×|E|) For complete graph = |E| = $\dfrac{n(n-1)}{2}$             |V| = n             $\therefore$$\Theta$$\left( n \times \dfrac{n(n-1)}{2} \right) = \Theta(n2)$

Keep practicing — related questions