Creating an O(n log n) time and O(n) space algorithm for counting pairs in an array
Just evaluate $\binom k2$ with $\frac{k(k-1)}2$, this takes $O(1)$.



Note that if the pairs are to be counted "without replacement", the formula is $\lfloor\frac k2\rfloor$.