# Hopcroft–Karp algorithm time complexity

In the last 2 paragraphs of the paper about Hopcroft–Karp algorithm to find the maximum cardinality matching in bipartite graph:

https://dl.dropboxusercontent.com/u/64823035/04569670.pdf

The execution time of a phase is O(m+n), where m is the number of edges in G, and n is the number of vertices. Hence the execution time of the entire algorithm is O((m+n)s), where s is the cardinality of a maximum matching.

If G has n vertices then m <= n^2 / 4 and s < n / 2 so that the execution time is bounded by O(n^(5/2)).

I don't understand given:

m <= n^2 / 4
s <= n / 2


why they concluded:

O((m+n)s) = O(n^(5/2))


Shouldn't it be:

O((m+n)s) = O(n^3)


Any idea?

• This is explained on Wikipedia. Remember to research the problem yourself before asking here. – David Richerby Jan 3 '14 at 16:01
• Thanks. I had referred this Wikipedia before, but was not sure if I should trust Wikipedia or the original algorithm's paper. – An Phung Jan 3 '14 at 16:18
• Corollary 5 of the paper says there are only $O(\sqrt{s})$ phases. – David Richerby Jan 3 '14 at 16:23
• That must be it. I think they forgot to draw the $\sqrt{}$ symbol. – An Phung Jan 3 '14 at 16:33
• There does seem to be a space left for it on the fifth-to-last line of the paper before the references (they write O((m+n) s) instead of O((m+n)s); compare the sixth-to-last line of the first column of p122). Isn't it good that we don't have to typeset papers that way any more? – David Richerby Jan 3 '14 at 16:41