a) If a heap is used to represent a priority queue, and the first element is removed, the heap property is restored by moving the last element to the root of the tree, and then running MAX-HEAPIFY on the new root element. What is the worst-case complexity of restoring the heap property in this way?

b) The first step of the heapsort algorithm converts the input array into a max heap using a function called BUILD-MAX-HEAP. Surprisingly, the worst- case complexity of this function is linear in the size n of the input array.

c) Consider a large, unsorted file of records that contains many duplicates of the same records. (One record is a duplicate of another if it has the same record number.) Consider the problem of removing all of the duplicates, so that the file contains a unique copy of each record. Describe a simple algorithm that removes all duplicates and runs in O(n log n) time, where n is the number of records in the file.

d) Consider the following recurrence: T (n) = 3T(n/2) + n. Indicate which case b of the Master theorem applies (first, second, or third), and solve the recurrence.

 

Transcribed Image Text:

The following recursive algorithm finds the sum of all elements in an array using a divide and conquer strategy. func sumArray(A, low, high) if low > high return 0 if low = high %3D return A[low] mid <- (high + low) / 2 leftSum <- sumArray (A, low, mid) rightSum <- sumArray (A, mid+1, high) return leftSum + rightSum Give a recurrence relation for the worst-case performance of this algorithm, and then se the Master theorem to find the asymptotic complexity of your recurrence relation. The following recursive algorithm finds the sum of all elements in an array using a divide and conquer strategy. func sumArray(A, low, high) if low > high return 0 if low = high %3D return A[low] mid <- (high + low) / 2 leftSum <- sumArray (A, low, mid) rightSum <- sumArray (A, mid+1, high) return leftSum + rightSum Give a recurrence relation for the worst-case performance of this algorithm, and then se the Master theorem to find the asymptotic complexity of your recurrence relation.

Answer rating: 100% (QA)

Part a The worst case time complexity to restore the heap property is Ologn because at a time it wil... View the full answer