Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have two datasets with $n$ and $m$ points. To find the match I have to compare each point in one data set with the other data set which makes the complexity $O(m\times n)$. I did some heuristics and divided the whole problem into smaller parts; say, $r$ parts. Now data sets one and two both are divided into $r$ parts and I only have to search in the corresponding parts but not the whole dataset. What would be the complexity of it? If the points are the same in every partition lets say $k$ points then the complexity in my point of view will be $O(r\times k^2)$. In my case the data sets points are not the same in every partition.

What will be the complexity in this case?

Thanks a lot.

share|cite|improve this question
I would think that you would have to take into account the complexity of figuring out how to divide the sets into $r$ parts. – Gerry Myerson Oct 11 '11 at 1:17
If you continue down your line of reasoning you'll get to kd-trees. As a side note- you can put the $n$ points into a hash table and then iterate over the $m$ points to check for inclusion. Building the hash table takes $O(n)$ time and searching for inclusion takes $O(m)$ giving you $O(m + n)$ behavior. – GEL Oct 11 '11 at 4:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.