algorithmperformanceclosest-points

Closest pair of points brute-force; Why O(n^2)?

I feel stupid for asking this question, but...

For the "closest pair of points" problem (see this if unfamiliar with it), why is the worst-case running time of the brute-force algorithm O(n^2)?

If say n = 4, then there would only be 12 possible pair of points to compare in the search space, if we also consider comparing two points from either direction. If we don't compare two points twice, then it's going to be 6.

O(n^2) doesn't add up to me.

Solution

  • The actual number of comparisons is:

    exact formula, or enter image description here.

    But, in big-O notation, you are only concerned about the dominant term. At very large values of enter image description here, the enter image description here term becomes less important, as does the enter image description here coefficient on the <code>n^2</code> term. So, we just say it's <code>O(n^2)</code>.

    Big-O notation isn't meant to give you the exact formula for the time taken or number of steps. It only gives you the order of the complexity/time so you can get a sense of how it scales for large inputs.