What is the running time of the Floyd Warshall Algorithm?(a) Big-oh(V)(b) Theta(V^2)(c) Big-Oh(VE)(d) Theta(V^3)I got this question during an interview.I want to ask this question from Shortest Path topic in section Shortest Path of Data Structures & Algorithms II

What is the running time of the Floyd Warshall Algorithm?(a) Big-oh(V)

1.	What is the running time of the Floyd Warshall Algorithm?(a) Big-oh(V)(b) Theta(V^2)(c) Big-Oh(VE)(d) Theta(V^3)I got this question during an interview.I want to ask this question from Shortest Path topic in section Shortest Path of Data Structures & Algorithms II
Answer» Right ANSWER is (d) Theta(V^3) Explanation: The running TIME of the Floyd Warshall algorithm is determined by the TRIPLY nested for LOOPS. Since each execution of the for LOOP takes O(1) time, the algorithm runs in time Theta(V^3).

Discussion

No Comment Found

Related InterviewSolutions

What is the formula to compute the transitive closure of a graph?(a) tij(k) = tij(k-1) AND (tik(k-1) OR tkj(k-1))(b) tij(k) = tij(k-1) OR (tik(k-1) AND tkj(k-1))(c) tij(k) = tij(k-1) AND (tik(k-1) AND tkj(k-1))(d) tij(k) = tij(k-1) OR (tik(k-1) OR tkj(k-1))The question was posed to me in unit test.This intriguing question comes from Shortest Path topic in section Shortest Path of Data Structures & Algorithms II
In the given graph, how many intermediate vertices are required to travel from node a to node e at a minimum cost?(a) 2(b) 0(c) 1(d) 3The question was asked in exam.I need to ask this question from Shortest Path in division Shortest Path of Data Structures & Algorithms II
In the given graph, what is the minimum cost to travel from vertex 1 to vertex 3?(a) 3(b) 2(c) 10(d) -3The question was asked during an online exam.My question is taken from Shortest Path in section Shortest Path of Data Structures & Algorithms II
The time taken to compute the transitive closure of a graph is Theta(n^2).(a) True(b) FalseI have been asked this question in final exam.Asked question is from Shortest Path topic in section Shortest Path of Data Structures & Algorithms II
Using logical operator’s instead arithmetic operators saves time and space.(a) True(b) FalseI got this question in quiz.This key question is from Shortest Path topic in division Shortest Path of Data Structures & Algorithms II
What happens when the value of k is 0 in the Floyd Warshall Algorithm?(a) 1 intermediate vertex(b) 0 intermediate vertex(c) N intermediate vertices(d) N-1 intermediate verticesThis question was addressed to me during an online exam.My query is from Shortest Path topic in division Shortest Path of Data Structures & Algorithms II
Who proposed the modern formulation of Floyd-Warshall Algorithm as three nested loops?(a) Robert Floyd(b) Stephen Warshall(c) Bernard Roy(d) Peter IngermanThe question was asked during an internship interview.Query is from Shortest Path topic in section Shortest Path of Data Structures & Algorithms II
Floyd- Warshall algorithm was proposed by ____________(a) Robert Floyd and Stephen Warshall(b) Stephen Floyd and Robert Warshall(c) Bernad Floyd and Robert Warshall(d) Robert Floyd and Bernad WarshallThe question was asked in semester exam.This question is from Shortest Path topic in portion Shortest Path of Data Structures & Algorithms II
What procedure is being followed in Floyd Warshall Algorithm?(a) Top down(b) Bottom up(c) Big bang(d) SandwichI had been asked this question in a job interview.This interesting question is from Shortest Path in section Shortest Path of Data Structures & Algorithms II
Floyd Warshall Algorithm can be used for finding _____________(a) Single source shortest path(b) Topological sort(c) Minimum spanning tree(d) Transitive closureThe question was posed to me in homework.My doubt stems from Shortest Path topic in chapter Shortest Path of Data Structures & Algorithms II

What is the running time of the Floyd Warshall Algorithm?(a) Big-oh(V)(b) Theta(V^2)(c) Big-Oh(VE)(d) Theta(V^3)I got this question during an interview.I want to ask this question from Shortest Path topic in section Shortest Path of Data Structures & Algorithms II

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment