If I have n points
A, B, C, D it seems like finding the closest pair via brute force search would go like:
- Compare A to every item (n-1)
- Compare B to every item (except A which it has already been compared to)
- etc for every element.
This seems like it would be less than $O(n^2)$ because the you are comparing to a progressively smaller number of elements each time you go to the next element.
Can someone explain to me why this is $O(n^2)$?