# Check distance between all elements in a list of numbers in O(n*lg(n))

I have an exercise for my algorithms and data structures class, where I basically have to implement a divide and conquer algorithm or function called check_distance to determine whether all numbers in a list X have distance greater or equal to k from each other, and I have to show that the worst case complexity of this algorithm is O(n*lg(n)).

When I think at algorithms that have to run in at most n*lg(n) time asymptotically, I think immediately about merge sort, which is exactly the divide and conquer algorithm that I used. Are my functions are correct or not?

Before this exercise, I had already one, where I had to create another divide and conquer function to check if there are duplicates in a list. This function should also run in O(n*lg(n)).

This is my function check_duplicates, which uses again the merge sort algorithm (I am not posting the code of the merge sort algorithm, because it's a typical merge sort. If you want me to post it, just ask!):

def check_duplicate(X):
S = merge_sort(X)               # O(n*lg(n))
for i in range(0, len(S) - 1):  # O(n)
if S[i] == S[i + 1]:
return True
return False


My first questions are: Is it correct, and does it run in O(n*lg(n)) time?

Now, I pass to the real problem, my second function, which (as I said) should check that the distance between each element in a list is greater or equal than a constant k. For this check_distance function, I used the check_duplicate function above, to ensure that are no duplicates, otherwise it returns immediately false.

Now, my main reasoning was again to sort the list. Once the list is sorted, the ai + 1 element will always be greater or equal than ai, therefore, for all ai in X, ai <= ai + 1 <= ai + 2, etc.

Now, again, for all ai in X, if I sum ai + k, and this is less or equal than ai + 1, then the distance between all elements should be >= k.

Am I correct?

def check_distance(X, k):
if check_duplicate(X):        # n*lg(n)
return False
else:                         # no duplicate values
A = merge_sort(X)
for i in range(len(A) - 1):
if A[i] + k > A[i + 1]:
return False
return True


If I am not correct, is there a better approach?

• The check_duplicate is not needed. And your code will break on 1 set element. Also what about negative k ? Mar 31, 2015 at 9:25
• «all numbers in a list X have distance greater or equal to k from each other» is a bit unclear to me. What is "each other" — just neighbors or an arbitrary other number in the list? For the former, an O(N) solution is obvious, for the latter, an O(N log N) solution with sorting is also obvious.
– 9000
May 2, 2015 at 1:34
• @9000 He already has both of those solutions, and both the O(n log n) requirement and him sorting make rather clear that it's not about neighbors in the original order. May 2, 2015 at 1:41
• @StefanPochmann: While I understand that everything hints to a sort-oriented solution, I'd prefer a stricter problem statement. For instance, the 'divide and conquer' hint is not entirely applicable to sorting solution: quicksort does classic divide and conquer, merge sort works a bit differently (and BTW merge sort is always O(N log N), quicksort isn't).
– 9000
May 2, 2015 at 1:55

I guess you don't need this anymore, but since I realized gnasher's bump only after thinking about this, I'll leave some imho nicer code here anyway:

def check_distance(X, k):
A = merge_sort(X)
return all(b-a >= k for a, b in zip(A, A[1:]))


I'm interested in the teacher's solution. Did he just have this braindead sort and sweep in mind, or something more interesting?

The obvious solution is to sort the array in O (n log n), and then the elements can be checked sequentially in O (n). I wonder what is going on in the teachers mind when he asks for a "divide and conquer" algorithm.

check_duplicate is redundant. The list must not be sorted because sorting rearanges elements.

Calculate the difference between two consecutive elements and compare the value against k.

def check_distance(x, k):
l = len(x)
if l in [0,1]:
return False

for i in range(l-1):
if x[i+1] - x[i] < k:
return False
return True


Using recursion,

def check_dist(x,k):
l = len(x)
if l == 2:
return x - x >= k
if l in (0,1):
return False
return x - x >= k and check_dist(x[1:],k)

• I wonder if yours is divide and conquer. Apr 3, 2015 at 16:21
• You are iterating over result of the sort. It doesn't matter if it's merge or bubble, it's a sorting. If x2 => x1+k it's already sorted. If x = 5,2 and k = 1,2,3 your code gives True, because you sort. For the given result k should be k >= -3 Apr 3, 2015 at 16:54