Now consider the following generalization of the problem:Given the array A and a

Question

Now consider the following generalization of the problem:Given the array A and
an integer k < n, we want an algorithm that determines whetherthe array contains a value
that occurs more than n/k times in it (if many such values exist,then it is enough to find one of them).

Design an algorithm for doing this, and analyze its complexity as afunction of n and k.
Your grade on this question will depend on how fast your algorithmis
(of course it also has to be correct). Full credit is for an O(nlog k) time algorithm. Now consider the following generalization of the problem:Given the array A and
an integer k < n, we want an algorithm that determines whetherthe array contains a value
that occurs more than n/k times in it (if many such values exist,then it is enough to find one of them).

Design an algorithm for doing this, and analyze its complexity as afunction of n and k.
Your grade on this question will depend on how fast your algorithmis
(of course it also has to be correct). Full credit is for an O(nlog k) time algorithm.

Explanation / Answer

             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)).

In particular, for m = n the time complexity is O(c1k + cn log k), which is O(n log k).

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

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