Consider a set S of n greaterthanorequalto 2 distinct numbers all greater than z
ID: 3804618 • Letter: C
Question
Consider a set S of n greaterthanorequalto 2 distinct numbers all greater than zero in unsorted order For each of the problems below Give an algorithm to determine two distinct numbers x and y in the set S that satisfy the condition(s) of the problem Your algorithm must be specified using pseudocode in the style of the text You must justify that your algorithm has the requested run time in O (n log n) time, determine x.y element S such that x notequalto y and |x - y| lessthanorequalto |w - z| for all w. z element S such that w notequalto z. in O (n) time, determine x. y element S such that |x - y| greaterthanorequalto |w - z| for all w z element S for all w. z element S such that w notequalto z.Explanation / Answer
1. sort the array element in increasing order.
2. min_diff
3. x -1
4. y -1
5. for i1 to n
6. if (|arr[i+1] – arr[i]| < min_diff) and (arr[i+1] arr[i])
7. min_diff |arr[i+1] – arr[i]|
8. x arr[i]
9. y arr[i+1]
step-1, takes O(nlogn) time to sort, and step-2 to 8 takes O(n) time since we just traversing the array once
1. max_elem arr[1]
2. min_elem arr[1]
3. for i2 to n
4. if max_elem < arr[i]
5. max_elem = arr[i]
6. if min_elem > arr[i]
7. min_elem = arr[i]
8. if min_elem max_elem
9. return |min_elem - max_elem|
The above alogrithm takes only O(n) times as we are traversing the array only once to find the minimum and maximum element