The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+17 votes

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

- $\theta(n^2)$
- $\theta(n^2\log n)$
- $\theta(n^3)$
- $\theta(n^3\log n)$

+35 votes

Best answer

Time complexity of Bellman-Ford algorithm is $\Theta(|V||E|)$ where $|V|$ is number of vertices and $|E|$ is number of edges. If the graph is complete, the value of $|E|$ becomes $\Theta\left(|V|^2\right)$. So overall time complexity becomes $\Theta\left(|V|^3\right)$. And given here is $n$ vertices. So, the answer ends up to be $\Theta\left(n^3\right)$.

+11 votes

as we know time complexity of bellman-ford is O(En) where E is no of edges and n is no of vertices

and in complete graph no of edges is E=n(n-1)/2 where n is no of vertices

here E=O(n^{2})

so time complexity of bellman-ford algorithm on complete graph with n vertices is O(n^{3})

so ans is C.)

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.9k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 447
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

37,939 questions

45,453 answers

131,195 comments

48,209 users