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

[Paul Kislanko]

> -----Original Message-----
> From: election-methods-electorama.com-bounces at electorama.com 
> [mailto:election-methods-electorama.com-bounces at electorama.com
> ] On Behalf Of Ted Stern
> Sent: Thursday, January 06, 2005 4:52 PM
> To: election-methods at electorama.com
> Subject: [EM] Re: There is always a Condorcet Winner! (among 
> all lotteriesof candidates :-)
> 
> On 6 Jan 2005 at 14:31 PST, Markus Schulze wrote:
> > Dear Jobst,
> >
> > you wrote (5 Jan 2005):
> >> By the way, is it possible to prove a Beatpath winner
> >> in O(n^2) time also?
> >
> > 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))