The runtime for this algorithm is $$$O(n^3)$$$, but I've seen at least two problems where the intended solution is using this algorithm and $$$N = 1000$$$. (The ones I'm thinking of are: https://open.kattis.com/problems/engaging and https://open.kattis.com/problems/cordonbleu ). It runs in under 1.5 seconds for both. That's about 7 times faster than I'd expect if we actually had to use $$$1000^3 = 10^9$$$ operations. My main concern is being able to estimate how long the algorithm will take to run, in a contest setting. Is it possible to generate a worst case where we need all $$$n^3$$$ operations? Does this algorithm have a provably low-constant factor for being $$$O(n^3)$$$? Or is it like a flow problem, where we can say a strict upper-bound and know that the algorithm will usually out-perform this estimate, but it's harder to give a precise estimate? Given what I know about the similarities with flow, I'm guessing it's the latter, but I wanted to ask if there's a better way to estimate how long this algorithm will take to run.

(Just FTR I've read the KACTL implementation, and kind of understand how it works, but it's not obvious how many times that inner while loop is called while updating potentials).