[EM] Re: There is always a Condorcet Winner! (among all lotteriesof candidates :-)

[Ted Stern]

On 6 Jan 2005 at 15:15 PST, Paul Kislanko wrote:
>> On 6 Jan 2005 at 14:31 PST, Markus Schulze wrote:
   <snip>

>> > Well, with the Dijkstra algorithm you can calculate
>> > in O(n^2) time the strengths of the strongest paths from
>> > candidate A to every other candidate and from every other
>> > candidate to candidate A.
>> >
>> > Markus Schulze
>> 
>> But that still leaves you with another order of n to calculate the winner
>> out of n candidates, right?  So the answer would be no, by all appearances.
>
> Technically, if a problem can be solved in O(N^2) time, an additional step
> that uses only O(N^1) time mens the problem can still be solved in O(N^2)
> time, so the answer would be "yes, by all appearances" if the extra step is
> only of O(N).
>
> O(final) = MAX(O(intermediates))

Hi Paul --

I understand the technicalities, explain how you avoid running the Dijkstra
algorithm N times.

Ted
-- 
Send real replies to
	ted stern at u dot washington dot edu

Frango ut patefaciam -- I break that I may reveal