0

I'm wondering if someone could break down this big O notation for me because this still kind of eludes me.

Two data frames: A of size n x 2 and B of size m x 2, both of type numeric. Assume each row is a coordinate pair.

We must find which coordinate pair in A is closest to which coordinate pair in B.

Pseudocode:

x = NULL

for i in length(A)
  for j in length(B)
    x[i,j] = sqrt((A[i,1] - B[j,1])^2 + (A[i,2] - B[j,2])^2)
which.min(x)

I'm not sure if that pseudocode is perfect, but I think you get the idea.

My guess is that this is $O(n^2)$ because there is a nested for loop, but I may be missing something.

conv3d
  • 161
  • What is which.min(x)? Also, if you are looking for the smallest distance, don't bother with the square root - just do it at the end. – marty cohen Dec 28 '17 at 00:21
  • Yea, that's a good point. which.min just checks for the minimum value in the list and then returns the index of that value in the data frame – conv3d Dec 28 '17 at 00:24
  • If you just want the minimum value and its index, just check at each point and, if it is the min, store that. There is no need for the array x[i, j]. – marty cohen Dec 28 '17 at 00:30

1 Answers1

1

The for loop has $O(mn)$, since it iterates through all of $B$ once ($m$ comparisons) for each row of $A$ ($n$ times). It looks like the minimum function has $mn$ values and it can take at most linear time to run (usually less). So the overall algorithm runs in $O(mn)$ time.

user2825632
  • 2,881