What is the efficiency of Gale-Shapley algorithm used in stable marriage problem?(a) O(N)(b) O(N log N)(c) O(N^2)(d) O(log N)The question was asked during an interview for a job.This key question is from Matching in portion Matching of Data Structures & Algorithms II

What is the efficiency of Gale-Shapley algorithm used in stable marria

1.	What is the efficiency of Gale-Shapley algorithm used in stable marriage problem?(a) O(N)(b) O(N log N)(c) O(N^2)(d) O(log N)The question was asked during an interview for a job.This key question is from Matching in portion Matching of Data Structures & Algorithms II
Answer» Right OPTION is (c) O(N^2) Easiest explanation - The TIME efficiency of Gale-Shapley algorithm is MATHEMATICALLY FOUND to be O(N^2) where N denotes stable MARRIAGE problem.

Discussion

No Comment Found

Related InterviewSolutions

From the given graph, how many vertices can be matched using maximum matching in bipartite graph algorithm?(a) 5(b) 4(c) 3(d) 2I had been asked this question in homework.My enquiry is from Matching in section Matching of Data Structures & Algorithms II
Who was the first person to solve the maximum matching problem?(a) Jack Edmonds(b) Hopcroft(c) Karp(d) Claude BergeI had been asked this question in class test.This interesting question is from Matching topic in section Matching of Data Structures & Algorithms II
What is the efficiency of algorithm designed by Hopcroft and Karp?(a) O(n+m)(b) O(n(n+m)(c) O(√n(n+m))(d) O(n+2)I had been asked this question in final exam.My question is taken from Matching in division Matching of Data Structures & Algorithms II
What is the total number of iterations used in a maximum- matching algorithm?(a) [n/2](b) [n/3](c) [n/2]+n(d) [n/2]+1The question was posed to me in class test.This interesting question is from Matching in section Matching of Data Structures & Algorithms II
The problem of maximizing the sum of weights on edges connecting matched pairs of vertices is?(a) Maximum- mass matching(b) Maximum bipartite matching(c) Maximum weight matching(d) Maximum node matchingThe question was asked in an online interview.This is a very interesting question from Matching in portion Matching of Data Structures & Algorithms II
Which is the correct technique for finding a maximum matching in a graph?(a) DFS traversal(b) BFS traversal(c) Shortest path traversal(d) Heap order traversalThe question was posed to me in homework.My question is from Matching in division Matching of Data Structures & Algorithms II
Which one of the following is an application for matching?(a) Proposal of marriage(b) Pairing boys and girls for a dance(c) Arranging elements in a set(d) Finding the shortest traversal pathThis question was posed to me in my homework.The origin of the question is Matching topic in chapter Matching of Data Structures & Algorithms II
A matching M is maximal if and only if there exists no augmenting path with respect to M.(a) True(b) FalseThe question was posed to me in unit test.This question is from Matching in portion Matching of Data Structures & Algorithms II
In a bipartite graph G=(V,U,E), the matching of a free vertex in V to a free vertex in U is called?(a) Bipartite matching(b) Cardinality matching(c) Augmenting(d) Weight matchingThis question was addressed to me in a national level competition.I need to ask this question from Matching topic in portion Matching of Data Structures & Algorithms II
What is the length of an augmenting path?(a) Even(b) Odd(c) Depends on graph(d) 1This question was addressed to me during an interview for a job.I want to ask this question from Matching in section Matching of Data Structures & Algorithms II

What is the efficiency of Gale-Shapley algorithm used in stable marriage problem?(a) O(N)(b) O(N log N)(c) O(N^2)(d) O(log N)The question was asked during an interview for a job.This key question is from Matching in portion Matching of Data Structures & Algorithms II

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment