Therefore, the first √''n'' phases, in a graph with ''n'' vertices and ''m'' edges, take time O(''m'' √''n'').
OnceIt can be shown that each phase increases the length of the shortest augmenting path by at least one: the phase finds a maximal set of augmenting paths of the given length, so any remaining augmenting path must be longer. Therefore, once this number of initial phases is complete, the shortest remaining augmenting path has at least √''n'' edges in it. However, the eventual optimal matching differs from the partial matching ''M'' found by the initial phases in a collection of vertex-disjoint augmenting paths and alternating cycles. If each of the paths in this collection has length at least √''n'', there can be at most √''n'' paths in the collection, and the size of the optimal matching can differ from the size of ''M'' by at most √''n'' edges. Since each phase of the algorithm increases the size of the matching by at least one, there can be at most √''n'' additional phases before the algorithm terminates.
Since the algorithm performs a total of at most 2√''n'' phases, it takes a total time of O(''m'' √''n'').
