My vote: O(n Log n +n))

While I suck at math, I’m pretty sure that the fastest way to detect a duplicate would be the (n log n) +n described. As even comparing the complete equation of (((n^2)-n)/2) it is still superior.