Question

3. Suppose we want to find the 2nd largest and 2nd smallest elements simultaneously for an input of n numbers stored in an array A[1:n]. Compare the following strategies in terms of their exact number of comparisons. Strategy 1: adapt the two separate For loops idea for minimum and maximum. Strategy 2: Run mergesort to sort the numbers in ascending or descending order, then output the 2nd ranked and (n-1)th ranked elements. First write each algorithm in pseudocde, then analyze the exact number of comparisons required by the algorithm. Note, asymptotic calculations will only get you partial credit for this problem. Can you find a better strategy for this problem than the two given? If yes, write the algorithm and analyze the exact number of comparisons required by the algorithm. If not, prove that one of the given strategies is optimal.

Answer 1

Scenario 1:

If we use 2 separate  for  loops for finding the second minimum and second maximum, the time complexity will be O(2n).

Algorithm with 2 for loops

Initialize 4 variables max,secondMax,min and secondMin as,    max = secondMax = min = secondMin = arr[1] // initialize to start element of array Start traversing the array, If the current element in array say arr[i] is greater than max. Then update max and secondMax as, secondMax = max max = arr[i] Else If the current element is greater than secondMax secondMax = arr[i] Print the value of secondMax.       Start traversing the array, If the current element in array say arr[i] is less than min. Then update min and secondMin as, secondMin = min min = arr[i] Else If the current element is less than secondMin secondMin = arr[i] Print the value of secondMin.

Scenario 2 :

Merge sort uses Divide and Conquer approach. And it takes O(n log(n)), finding an element takes O(1) time complexity.

• If it is only one element in the list it is already sorted, return.
• Divide the list recursively into two halves until it can no more be divided.
• Merge the smaller lists into new list in sorted order.

For more information please refer those images below:

#######Please give a positive rating for this answer.This helps me write more. Thank you. Have a nice day#######