1

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?

  • There's at leat one problem with my algorithm, which I have already solved. If k == 0, it means that we can also have duplicates. So the first if should be if k > 0 and check_duplicate(X): – nbro Mar 30 '15 at 21:24
  • Actually, I don't even need this statement: if k > 0 and check_duplicate(X)... – nbro Mar 30 '15 at 22:49
  • 1
    The check_duplicate is not needed. And your code will break on 1 set element. Also what about negative k ? – Pieter B Mar 31 '15 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 '15 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. – Stefan Pochmann May 2 '15 at 1:41
1

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.

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?

0

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)
  • This is not a divide and conquer solution. – nbro Apr 3 '15 at 16:07
  • I wonder if yours is divide and conquer. – Nizam Mohamed Apr 3 '15 at 16:21
  • 2
    It is for sure a divide a conquer algorithm because of merge sort. – nbro Apr 3 '15 at 16:39
  • 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 – Nizam Mohamed Apr 3 '15 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.