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