# Is there an example of Dinitz's algorithm running with the worst time complexity?

I am trying to find a network, where Dinic's algorithm makes $$|V|^2*|E|$$ steps. Clearly it cannot be a network with $$3$$ or less vertices, but I am not able to come up with a working example for quite a while now.

Any idea?

• What exactly is a "step" to you? Also, if you want to gain any form of helpful understanding, you'll have to come up with a pattern that scales to arbitrary size; finite example sets don't have any bearing on $O$-asymptotics. – Raphael Nov 13 '18 at 15:00

1. Dinic's algorithm runs in $O(|V|^2 \cdot |E|)$ time, so it might never make $|V|^2 \cdot |E|$ steps.
2. Finding a single example is insufficient, as any finite-size counterexample can be "hidden" as a constant in asymptotic notation. You will need an infinite sequence of networks of strictly increasing size with a lower time bound of $\Omega(|V|^2 \cdot |E|)$ to prove that the bound is indeed tight.