[EM] finding the beat path winner with just one pass through the ranked pairs

[Rob LeGrand]

Markus wrote:
> the runtime to calculate the strongest path from
> every candidate to every other candidate is O(C^3).
> However, the runtime to sort O(C^2) pairwise defeats
> is already O(C^4). So you cannot get a faster
> algorithm by sorting the pairwise defeats.

Can't you sort O(C^2) items in O(C^2 log C) time if you use a O(n log n)
algorithm such as heapsort?

 
--
Rob LeGrand
rob at approvalvoting.org
Citizens for Approval Voting
http://www.approvalvoting.org/