1
$\begingroup$

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.

  • 0
    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.2011-10-11

0 Answers 0