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.)

|x-y| will be maximum when y is the minimum element and x is the maximum element

Thus we can find minima in the array in O(n) by

Start i=0 and iterate it till n-1

If (a(i+1) < min))

   min=a(i+1),

else

min=min

Similarly to find maximum,

If (a(i+1) > max)

max=a(i+1),

else

max=max

Thus total time n+n = 2n =O(n)

And thus we can compute |x-y| after finding minima and maxima of array by |x-y| = |max - min|

b.)

|x-y| = | a[n-1] - a[0] |
Thus O(1)

c.)

Use merge sort to sort the array

It takes O(n*logn)

Then initialize i=0 and move till n-1

If ( | a[i+1] - a[i] | < z)

     z = | a[i+1] - a[i] |

else

      z = z

|x-y| = z

Total time taken = nlog(n) + n = O(n*logn)

d.)

The array is already sorted

Hence,

initialize i=0 and move till n-1

If ( | a[i+1] - a[i] | < z)

     z = | a[i+1] - a[i] |

else

      z = z

|x-y| = z

Total time taken =   n = O(n)

Let me know if anything is unclear

Cheers :)

Harshit

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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