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.

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

Explanation / Answer

We have a sorted 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 sorted, minimum difference will be found between adjacent elements in the given array. So, we just need to iterate through the array and find the difference between adjacent elements and keep track of the elements which produce minimum value

2. In the worst case, we need to iterate through the complete array. Complexity will be O(N)

FUNCTION MIN_DIFF(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.