Hopcroft–Karp algorithm time complexity

Question

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.

Answer 1

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.