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) tiem algorithm which finds the two numbers x,y,x>y from A such that the difference between them is as large as possible. i.e.x-y is maximized.For example,if an input is A=6,2,10000,8,the output should be x=10000,y=2.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 maximized.
1. Maximum difference is possible when one number if the maximum and another number is minimum of the array. So, we just need to iterate through the array and find the maximum and minimum elements.

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

FUNCTION MAXDIFF(ARR[])
   MIN = MAX_INT
   MAX = MIN_INT
   FOR I IN 1...SIZE(ARR)
       IF ARR[I] < MIN  
           MIN = ARR[i]
       IF ARR[i] > MAX
           MAX = ARR[i]
   PRINT "X = "+MAX+" , Y = "+MIN

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

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