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 ---- Election-methods mailing list - see http://electorama.com/em for list info