Question

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

Answer 1

Right choice is (c) O(√n(n+m))

To explain: The efficiency of algorithm designed by Hopcroft and Karp is mathematically found to be O(√n(n+m)).