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

Question

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 a_{i + 1} element will always be greater or equal than a_i, therefore, for all a_i in X, a_i <= a_{i + 1} <= a_{i + 2}, etc.

Now, again, for all a_i in X, if I sum a_i + k, and this is less or equal than a_{i + 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?

Answer 1

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?

Answer 2

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.

Answer 3

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[1] - x[0] >= k
    if l in (0,1):
        return False
    return x[1] - x[0] >= k and check_dist(x[1:],k)