0
$\begingroup$

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)$?

$\endgroup$
2
$\begingroup$

It's not clear what you think $O(n^2)$ means. $O(n^2)$ means that there is a constant $c$ so that, when $n$ is large enough, your algorithm takes no more than $cn^2$ time.

As you observed, the algorithm takes $(n-1)+(n-2) + \ldots + 1 $ time. This is equal to $\frac12 (n^2-n)$. This quantity is less than $2n^2$ whenever $n$ is larger than $10$. So it is indeed $O(n^2)$.

Another way to understand $O(n^2)$ is: if $n$ doubles, the algorithm will take about four times as long. For $n=10$, your algorithm takes $9+8+\ldots + 1 = 45$ steps. When $n=20$, it takes $ 19+18+\ldots + 1 = 190$ steps. That is indeed pretty close to $4\cdot 45=180$ steps. Similarly when $n=40$ it takes $780$ steps, which is again pretty close to $4\cdot 190 = 760$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Here's a hint. Break the question into two parts:

  1. Given $n$ elements, compute the (exact) number $C$ of comparisons following your scheme. If you are stuck here, (i) look at gradually growing examples and see how $C$ behaves and (ii) try to express $C$ as a sum and perhaps use a suitable sum identity.

  2. Prove that $C = O(n^2)$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Your problem is equivalent to determining the number of edges in a complete graph with $n$ nodes and undirected edges.

Model each point as a node of a graph. You now have a graph with $n$ nodes. You have to look at the relation between every pair of nodes. This is equivalent to iterating over all edges precisely once. That means that you need to consider the number of edges.

As every of those $n$ nodes is connected to $n-1$ other nodes, and you want to avoid counting edges twice, the number of edges is $\frac{n(n-1)}{2}$.

Show that this is in $\mathcal{O}(n^2)$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

o(n^2) means that n^2 is an upper bound. So even if it is smaller than n^2 but not so far from it, it still is o(n^2). Like 1/2 n^2 is also o(n^2)

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

The big-o notation ignores coefficients. Both $n^2$ and $n^2/2$ are $O(n^2)$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.