An element is the majority of a size-n array A [1...n] if it occurs more than...

Transcribed Image Text:

An element is the majority of a size-n array A [1...n] if it occurs more than 1 times in the array. Design a O(log n) time algorithm to find the majority of A in the EREW PRAM model using n processors where c is some constant. The smaller the constant c is, the better. Hint: adapt the algorithm in section 4 in this note Algorithm 5: Find majority 1 Function Majority (A[1...n]) /* take care of the case A has an odd number of elements if A is odd then Count A[1] in A. This takes O(n) time. if count >n/2 then else return A[1] | A=A[2...n] end if 2 3 4 5 6 7 8 9 for i=1,2,4,...,n/2 do 10 11 12 13 | if A[21] =A[21] then Add a copy of A[i] to B end for x = Majority(B) Count in A. If x is the majority of A, return r. Otherwise, return "no majority". The running time is given by the following recurrence T(n) = T(n/2) + O(n) which is O(n) by master theorem. An element is the majority of a size-n array A [1...n] if it occurs more than 1 times in the array. Design a O(log n) time algorithm to find the majority of A in the EREW PRAM model using n processors where c is some constant. The smaller the constant c is, the better. Hint: adapt the algorithm in section 4 in this note Algorithm 5: Find majority 1 Function Majority (A[1...n]) /* take care of the case A has an odd number of elements if A is odd then Count A[1] in A. This takes O(n) time. if count >n/2 then else return A[1] | A=A[2...n] end if 2 3 4 5 6 7 8 9 for i=1,2,4,...,n/2 do 10 11 12 13 | if A[21] =A[21] then Add a copy of A[i] to B end for x = Majority(B) Count in A. If x is the majority of A, return r. Otherwise, return "no majority". The running time is given by the following recurrence T(n) = T(n/2) + O(n) which is O(n) by master theorem.