[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