Question is from algorithm analysis &design. i)For each of the following problem

Question

Question is from algorithm analysis &design.

i)For each of the following problems,you have to find an efficient algorithm,and

1)Give a clear description of your algorithm for the problem.

2)state,what is the worse case analysis(use big-o notation)of your algorithm.

a)Let A be unsorted array(no repetitions)with n postitive integers.you have to find an O(n log n) time algorithm which finds the two numbers x,y,x>y from A such that the difference between them is as small as possible. i.e.x-y is minimized.For example,if an input is A=6,2,10000,8,the output should be x=8,y=6.Show your algorithm.

Explanation / Answer

We have an unsorted array of size n. We need to find two integes in the array such that their difference is minimum.
1. Since the given array is unsorted, minimum difference can be found between any two elements in the given array. So, we just need to iterate through all the pairs of the array and find the difference between elements and keep track of the elements which produce minimum value. But iterating through all the pairs will have the complexity of O(N^2). But we are interested in O(NlogN) algorithm.

2. Let's sort the array first. Sorting will take O(NlogN). Now all the elements in the array are sorted. Minimum difference will be found between adjacent elements. We just need to iterate through the array and find the difference between adjacent elements and keep track of the minimum

3. Total time complexity is, for sorting O(NLogN), iterating through the sorted array to find the minimum difference is O(N). Total = O(NlogN) + O(N) = O(NlogN)

FUNCTION MIN_DIFF(ARR[])
   SORT(ARR)
   MIN_IND = 1
   MIN_VALUE = INTEGER_MAX
   //Start from the second element in the array
   FOR I IN 2...SIZE(ARR)
       //Compare the adjacent element's difference and keep track of MIN   
       IF ARR[I]-ARR[I-1] < MIN_VALUE
           MIN_VALUE = ARR[I] - ARR[I-1]
           MIN_IND = I
   PRINT "X = "+ARR[MIN_IND]+" , Y = "+ARR[MIN_IND-1]

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

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