Detecting Condorcet Cycles
-
For any Smith compliant method, detecting a Condorcet cycle is easy given the method’s winner—you check if the winner is beaten head to head by some other candidate.
BTR is Smith compliant and the winner is fast to compute, therefore it yields very fast cycle detection. Specifically, we can determine existence of a cycle in worst-case linear time O(n) in n the number of candidates. Specifying the cycle is more complex, at worst O(n^2). I don’t think either can be improved. But just in case, what are some other comparably efficient methods to detect cycles?