Consider a set S of n >= 2 distinct numbers all greater than zero in unsorted or
ID: 3804034 • Letter: C
Question
Consider a set S of n >= 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.
a. in O(n lg n) time, determine x, y S such that x y and |x y| |w z| for all w, z S such that w z.
b. in O(n) time, determine x, y S such that |x y||w z| for all w, z S for all w, z S such that w z.
Explanation / Answer
a) Sort the set with any nlog(n) method. Then scan through the sorted set to find the smallest gap, thus the desired pair.
MinPair(S)
sort set
traverse array i = 0 to n
min s(i+1) - s(i)
This will take O(n) to traverse and find minimum gap. O(nlogn) for sorting
So total O(nlogn)
b) Check the first 3 integers in the set, and get rid of the middle one. Repeat this with the next integer from the set and continue until we are left with the desired pair of integers, leading to an algorithm that runs in O(n) worst-case time.
This will run in O(n) as every removed element will be checked only once and constant work is done to remove it. As there are max n elements to be removed it will take O(n) time.