> -----Original Message----- > From: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] > ] On Behalf Of Ted Stern > Sent: Thursday, January 06, 2005 4:52 PM > To: [EMAIL PROTECTED] > 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)) ---- Election-methods mailing list - see http://electorama.com/em for list info
