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?
Edited: Link fixed. My bad.
I believe you are correct and it seems to me there is an error in the paper - they significantly simplified the proof. Have a look at this paper where several Lemmas are used for the proof.