Count pairs without counting twice

Start with n × n choices. Remove the n self-comparisons. There are now n(n−1) ordered pairs. A–B and B–A represent the same unordered pair for birthday equality, so divide by 2.

Another way to see the formula is (n−1) + (n−2) + … + 1. For five cards this is 4 + 3 + 2 + 1 = 10. We also write this as “n choose 2”: choosing two different items without caring about their order.

Only halve reversed pairs when reversing the two items means the same test. “X is older than Y” has a direction; do not automatically treat every pair problem as symmetric. The pair totals here assume a complete scan without early stopping.

As n grows, the pair count grows roughly with n squared. Doubling a large n makes the work roughly four times as large. A fast computer still benefits from avoiding unnecessary work. Exact running time depends on the machine and what each comparison does; a fixed comparisons-per-second claim is only an illustration.