The k th quantiles of an n -element set A are the k 1 order statistics that divi

Question

The kth quantiles of an n-element set A are the k 1 order statistics that divide the sorted set into k equal-sized sets (to within 1). That is, the kth quantiles are Select(A, n/k), Select(A, 2n/k), …, Select(A, (k 1)n/k) (here we are assuming that k divides n). Finding the kth quantiles directly in this way would take O(nk) time.
Given an unsorted array A of n distinct keys and an integer k, with 1 k n, give an O(nlogk) algorithm to find the kth quantiles of A. You may assume that k divides n. You may assume that the linear-time (deterministic) Select algorithm (page 220) is available as a subroutine.

1. Describe your algorithm in pseudocode. Comment your code.

2. Prove that your algorithm is correct, i.e., argue that it returns the kth quantiles of A. Use induction.

3. Analyze the running time of your algorithm, i.e., explain carefully why your code runs in O(nlogk) time.

Explanation / Answer

A[] unsorted array

keys: an integer k

An empty array Q of length k – 1

To find : The kth quantiles of A.

QUANTILES(A,k,Q)

1. if k==1 then return

2. else

3.         n< length of A[]

4.         i <- k/2

5.         x <- SELECT(A,i.n/k)

6.         PARTITION(A,x)

7.         Add to list Q:QUANTILES(A[1] to A[i.n/k],k/2,Q)

8.         Add to list Q:QUANTILES(A[i.n/k + 1] to A[n],k/2,Q)

9.         return x

The algorithm first finds the key that turns out to be the lower median of Q, and then partitions the input array about this key. So there are two smaller arrays that each contain at most (k 1)/2 of the k 1 order of the original array A. At each level of the recursion the number of order statistics in the array is at most half the number of the previous array.

Consider a recurrsion tree.At the top level need to find k 1 order statistics, and it costs O(n) to find one. The root has two children, one contains at most 1 /2 order statistics, and the other 1 /2 order statistics. The sum of the costs for these two nodes is O(n).

At depth i ,2i order statistics are there. The sum of the costs of all nodes at depth i is O(n), for 0 i log2 (k 1), because the total number of elelements at any depth is n. The depth of the tree is d = log2(k 1). Hence, the worst-case running time of QAUNTILES is (n lg k).

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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