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
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
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 >=
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?