Suppose that, given an n-element array A (not sorted), we want anO(n) time algor
ID: 3608689 • Letter: S
Question
Suppose that, given an n-element array A (not sorted), we want anO(n) time algorithm
for determining whether the array contains a majority element,i.e., an element that occurs
more than n/2 times in the array. As explained in class, it is easyto solve this in O(n) time
by using the linear-time selection algorithm:
(i) Find the median (call it x), then (ii) count how many times x occurs in A.
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.
Suppose that, given an n-element array A (not sorted), we want anO(n) time algorithm
for determining whether the array contains a majority element,i.e., an element that occurs
more than n/2 times in the array. As explained in class, it is easyto solve this in O(n) time
by using the linear-time selection algorithm:
(i) Find the median (call it x), then (ii) count how many times x occurs in A.
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
A recursive procedure, for a set of size m where m <= n,initially (at the root of the binary recursion tree) we have m = nbut further down in the recursion tree we have m < n. We usek1 as shorthand for n/k, not as shorthand for m/k(because the definition of “majority” is relative tothe original set and not relative to the smaller subsets associatedwith non-root nodes of the recursion tree).
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)).
In particular, for m = n the time complexity is O(c1k + cn log k), which is O(n log k).
I hope this will helps toyou
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.