Give algorithms with the required worst-case time bounds for each of the followi

Question

Give algorithms with the required worst-case time bounds for each of the following
problems.
a) Given an unsorted array A of n integers, find the pair x,y?A that maximizes |x-y|. Your
algorithm must run in O(n) worst-case time.
b) Given a sorted array A of n integers, find the pair x,y?A that maximizes |x-y|. Your algorithm
must run in O(1) worst-case time.
c) Given an unsorted array A of n integers, find the pair x,y?A, x?y, that minimizes |x-y|. Your
algorithm must run in O(n logn) worst-case time.
d) Given a sorted array A of n integers, find the pair x,y?A, x?y, that minimizes |x-y|. Your
algorithm must run in O(n) worst-case time.

Explanation / Answer

A)

In this method, instead of taking difference of the picked element with every other element, we take the difference with the minimum element found so far. So we need to keep track of 2 things:
1) Maximum difference found so far (max_diff).
2) Minimum number visited so far (min_element).

O(n)

B)

Since the array is sorted Max x-y is A[n-1] - A[0] (last - first element)

O(1)

C) Sort the array using quicksort

then subract Middle two elements

O(nlogn)

D)

Since the array is already sorted, just travesre through the array to find middle two elements.

When the middle elements are found subtract them.

O(n)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.