On Dec 9, 2:52 am, sankethm7 <[email protected]> wrote: > Hello folks, > does anyone have idea to solve the problem given below: > > Assume that A[1…n] is an array > a. Describe an efficient parallel algorithm that uses n processors to > find the majority element of A > time complexity = O(n)
Couldn't you just use each processor x to compare A[x] with A[mod N x+2^step] step=0 to ceiling[ln N]-1 and replace A[x] with the max? If I've got it right (untested), with each step the number of times the maximum value appears doubles until it takes up the entire array. -- Geoff -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
