The task in this question is to compute the medians of all prefixes of an array.

Question

The task in this question is to compute the medians of all prefixes of an array. As input we are given the array A[1 . . n] of arbitrary integers. Using a heap data structure, design an algorithm that outputs another array M[1 . . n], so that M[i] is equal to the median of the numbers in the subarray A[1 . . i]. Recall that when i is odd, the median of A[1 . . i] is the element of rank (i + 1)/2 in the subarray, and when i is even, the median is the average of the elements with ranks i/2 and i/2 + 1. Your algorithm should run in worst-case time O(n log n). a. (20 marks) Describe your algorithm in clear and concise English, and also provide the corresponding pseudocode. Argue that your algorithm is correct. b. (4 marks) Justify why your algorithm runs in time O(n log n).

Explanation / Answer

lg(n!) >= (1/2) (n lg n - 1)

Combining both bounds :

1/2 (n lg n - 1) <= lg(n!) <= n lg n

By choosing lower bound constant greater than (1/2) we can compensate for -1 inside the bracket.

Thus lg(n!) = Theta(n lg n)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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