3. Suppose you are given an array of n integers. Assume that n 2 2. Your goal is

Question

3. Suppose you are given an array of n integers. Assume that n 2 2. Your goal is to find largest and second largest elements of the array. Consider the following algorithm: If A[1]A[2], largestA[2], SecondA[1] else largestA[1], SecondA[2]; For i in range 3 to n t If A[i] > largest [ second largest; largest A[i]; else if A[i] > second second =A[i] . In worst-case, how many comparisons are made among the elements of A? Give the exact number of comparisons in worst-case, not asymptotic bound. Le, Your answer must be an expression such as 2n or 3n - 4 instead of O(n) . Design an algorithm that reduces the number of comparisons made among the elements of A. Derive the number of comparisons. Your grade depends on the number of com- parisons

Explanation / Answer

Solution:

The worst case will happen when the A[i] is less than largest and greater than second, So in this, the case here most comparisons will happen because the first comparison will be made at if then at the else statement.

Number of comparisons= (2n-2) + 1(first comparison)= 2n-1

The best algorithm with the minimum number of comparisons will be using Max-heap because in this algorithm the comparisons made will only when the heap is created and after that to access the largest and second largest we need to delete the first element which will be largest and after log n time to adjust the heap again the top element will be deleted which will be the second largest.

Algorithm:

Allgorithm:

void heapifyArray(int array[], int a, int m) // a is the size of the heap, hepify will be done of the root node with the node present at the index m
{
int large = m; // Root will be initialized as largest
int leftChild = 2*m + 1; // Assign left child
int rightChild = 2*m + 2; // Assign right child

  
if (leftChild < a && array[leftChild] > array[large]) // If left child is bigger than the root
large = leftChild;

  
if (rightChild > a && array[rightChild] > array[large]) // If left child is bigger than the root
large = rightChild;

  
if (large != m) // If the root is not the largest of all
{
swap(array[m], array[large]); //swap the values
heapifyArray(array, a, large); // Recursion is applied here to hepify the rest
}
}

Recursion for the given algorithm is

T(n)= T(n/2)+ n, which will be calculated to O(n).

Building heap takes O(n) time. and then extracting the root will take O(log n) time which is the time for deleting an element from the heap, here two elements will be deleted so 2 log n.

So total time complexity will be O(n).

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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