For C candidates and V votes.
space does not include external storage of the votes, except for IRV which
effectively internalizes the whole vote set
| system | O-space | O-time |
|---|---|---|
| One Vote | C | V |
| Condorcet | C^2 | V*C^2 + C^4 |
| IRV a (traditional multi-pass) or IRNR | C*V | V*C^2 |
| IRV b (single pass, for when C is tiny and V is huge) | C! | V*C + C! |
| IRV c (linked-list buckets) | C*V | V*C |
| Borda or Rated | C | V*C + C log C |
There is an important 'caching' effect possible due to the loop order difference in the V*C^2 terms of Condorcet and IRV a. Condorcet is a single pass through the votes with C^2 work done on each. IRV a is C passes through V votes with C work done on each.
I feel like I may be missing some smallish terms in hose time descriptions.