I have a rather basic question about the number of operations taken by the Hopcroft-Karp algorithm for finding a maximum matching in a bipartite graph. It is commonly reported as $O(m \sqrt{n})$ where $m$ is the number of edges in the graph and $n$ is the number of vertices(for example, see wikipedia or this book, among many examples - I cannot post more than two links due to reputation constraints).

What bothers me about this is that if $m$ is small (say $m=n^{1/4}$) this seems to require less than $n$ iterations, which is odd: surely you have to at least look at every node, i.e., just to see if it has any incident edges or not?

Having looked at Hopcroft and Karp's original paper, I see they quote a running time of $O((m+n)\sqrt{n})$ which makes more sense.

So my question is: what is the reason why the running time of Hopcroft-Karp is usually quoted as $O(m \sqrt{n})$? Does this reflect an assumption that the graph is connected (I never see this stated explicitly)?

  • $\begingroup$ As a comment, big-oh notation measures the behaviour of a function as its arguments get larger. It's formally defined when there's only one variable, but here you have two. One of the dirty secrets of algorithm analysis is that there is no agreement on precisely what this means. When you say "if $m$ is small", someone might informally object that "well, big-oh only says what happens when $m$ gets large!" If that seems like a cop-out to you, you're not alone. See here for details: people.cis.ksu.edu/~rhowell/asymptotic.pdf $\endgroup$
    – Pseudonym
    Commented Jun 30, 2014 at 2:11
  • $\begingroup$ @Pseudonym: the OP doesn't say $m$ is small. He says $m=O(n^{1/4})$, which goes to infinity. $\endgroup$
    – user16034
    Commented Oct 12, 2015 at 7:12

1 Answer 1


The correct running time is indeed probably $O((m+n)\sqrt{n})$. However, this is a mouthful, and the expression $O(m\sqrt{n})$ looks nicer and is also more succinct. In most cases, $m \geq n/2$, since otherwise there is an isolated vertex. In fact, by finding isolated vertices, we can improve the running time of the algorithm to $O(n + m\sqrt{n})$.

An alternative way of stating the running time would be $O(m\sqrt{n})$, assuming $m \geq n$. The case of small $m$ is not so interesting (since then there are isolated vertices which can be eliminated), and so it is usually assumed that $m = \Omega(n)$.

  • 1
    $\begingroup$ Thank you! Another thought I had after writing the question is that perhaps the implicit assumption is that the graph is given as a list of edges. I think in that case, the running time is $O(m \sqrt{n})$. Could this be the assumption everyone is making when they write the time this way? $\endgroup$ Commented Jun 30, 2014 at 0:28
  • $\begingroup$ @Javin Right, that's another possible explanation. $\endgroup$ Commented Jun 30, 2014 at 0:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.