[EM] BeatpathWinner algorithm

Bart Ingles bartman at netgate.net
Thu Jun 2 08:16:33 PDT 2005


Markus Schulze wrote:
> ...  implementation
> had a runtime of O(NumberOfCandidates^5) while the Floyd algorithm
> has a runtime of O(NumberOfCandidates^3).

I wonder.  Was it really known whether the innermost loop could be 
entered n^4 times?

The number of nested loops is not the final determinant of runtime, 
although it obviously gives the worst case.  If it could be proven that 
the next-to-innermost loop is entered at most n times, then runtime 
would still be n^3.

Bart



More information about the Election-Methods mailing list