Suppose that, given ann-element array A (not sorted), we want an O(n) time algor

Question

Suppose that, given ann-element array A (not sorted), we want
an O(n) time algorithm for determining whether the array contains amajority element,
i.e., an element that occurs more than n/2 times in the array. Asexplained in class, it
is easy to solve this in O(n) time by using the linear-timeselection algorithm: (i) Find
the median (call it x), then (ii) count how many times x occurs inA. Now consider the
following generalization of the problem: Given the array A and aninteger k < n, we want
an algorithm that determines whether the array contains a valuethat occurs more than
n/k times in it (if many such values exist, then it is enough tofind one of them). Design an
algorithm for doing this, and analyze its complexity as a functionof n and k. Your grade on
this question will depend on how fast your algorithm is (of courseit also has to be correct).
Full credit is for an O(n log k) time algorithm.

Explanation / Answer

If k1 >= n then return the empty set (i.e., theoverall answer is “no such element exists”).Otherwiseuse the linear-time selection algorithm to find the median (call itx), then count how many times x occurs in A (say it occurs ctimes): if c > k1 then return x, otherwise do thefollowing. Compute a set A< of elements of A that areless than x, and a set A> of elements of A that aregreater than x. Observe that each of A< andA> has no more than n/2 elements (because x isthe median of set A). Recursively search A< for anelement that occurs more than k1 times. If there is suchan element then return it as the overall answer.

If no such element exists in A< then recursivelysearch A> for an element that occurs more thank1 times. If there is such an element then return it asthe overall answer. If no such element exists in A>then return the empty set (i.e., the overall answer is “nosuch element exists”). The recurrence for the time complexityis

             T(m) = c1 if m<= k1, and

            T(m) <=2T(m/2) + cm if m > k1

where c1 and c are constants. This implies that

           T(m)<= 2i T(m/2i) + icm

For details of this is so, see the way we guessed the solutionto the merge sort recurrence which is very similar to this one. Themajor difference from the merge sort recurrence is in the factthat, unlike merge sort where the “bottom” is hit whenm/2i = 2, here this occurs when m/2i firstbecomes smaller than k1, that is, for a value of i suchthat

         m/2i <= k0 < m/2i-1, and therefore i = (log(m/k1)).

This implies that

          T(m) =O((m/k1)T(k1) + cm log(m/k1))

                 = O(c1(m/k1) + cm log(m/k1)).

Replacing k1 by n/k in the above gives

       T(m) =O(c1(km/n) + cm log(km/n)).

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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