Consider an array Age with n elements representing the ages of individuals withi
ID: 3873874 • Letter: C
Question
Consider an array Age with n elements representing the ages of individuals within a group in arbitrary order. The following algorithm (given in Java-like pseudocode) outputs indexes of two individuals that are the closest in age among pairs of individuals whose ages are stored in the array. Note that f there is more than one pair of individuals with the same age difference we simply return one such pair. In the code below, abs(x) oompuies the absolute value of x. Far example, if Age(0]-26; Age[1-50; Age 21-15 Age[31-52, the algorithm will output 1 and 3 since individual 1 and 3 have age difference equals to 2, while any other pair of individuals have larger age difference. 2. int ninDifterenceabs (Age01-Age [11) tor 1-+1 1n +) int difterenceabs (Age11-Age I11) (ditference ninDifference) ninDitferencenditterence x-1: y-3 10 11. raturnx, y: A) (10 pt) Give the worst-case number of comparisons of array elements hat this B) (10 pt) Give a big-Oh estimate for the number of comparisons calculated C) (14 pt) Now, suppose the input array Age is given in sorted (increasing) arder. Give a D) (7 pt) Briefly jusity why the number of comparisons is O(n) algorithm performs (how many executions of ine 8) exactly, as a function of n. in the previous part. Justify your answer linear time algorithm that solves the same problem, i.e. your algorithm must perform number of comparisons that is O(n.Explanation / Answer
A). suppose n =7. Then outer loop will vary from 0 to 6.
when i =0, j have values from 1 to 6 ---> (n-1) comparison
when i = 1, j have values from 2 to 6 ---> (n-2) comparison
when i = 2, j have values from 3 to 6 ----> (n-3) comparison
when i = 3 , j have values from 4 to 6 ----> (n-4) comparison
when i = 4, j have values from 5 to 6 -----> (n-5) comparison
when i = 5 , j have value 6. -------> (n-6) comparison
Therefore when n = 7, the total number of comparison is (n-6) + (n-5) + (n-4) + (n-3) + (n-2) + (n-1) comparison = 6n -21 = 6*7 - 21 = 42 - 21 = 21 comparsons.
Generally we can say (n-1)n - k comparisons, where k is a constant.
In the above example n = 7, thus (7-1)(7) - 21comparisons.
B). Big-oh estimate
Big-oh will provide the upper limit of a value. In the above example it is clear that your number of comparisons can't go above n(n-1), also we are substracting a k from (n-1)n.
The loops are nested loops, so the if loop will execute for exactly n(n-1) times = n2-n times, When n becomes very larger number then n is negotiable with respect to n2
Thus the complexity with respect to comparisons become : O(n2)
C). Linear time algorithm to find minimum difference when Age list is sorted in ascending order
/************************** algorithm********************/
D). Analysis of above said algorithm
The for loop will run for i = 0 to n-1 times. The if condition is compared when i =0, i = 1, i = 3 ... upto
i = n-2. That means if comparison is done for n-2 times.
When n is a large number the big-oh can be represented as O(n) times.