Need Something Sorted? Sleep on It

Re:Need Something Sorted? Sleep on It by rileymat2 on Monday May 24, 2021 @10:03PM (#27271901)

If we are playing with this, why not take one pass to find the largest element, then another pass to divide each element in the list by that number, leaving it 3N+M/M.

Edit:

Why divide by m, when you can divide by M*C. Where C will speed this portion up by a factor!

[ Parent | on HN ]

Re:Need Something Sorted? Sleep on It by david_allison on Monday May 24, 2021 @10:40PM (#27272075)

Let's do better.

You can find the largest element in a list in O(1) time with n^2 processors[0]*.

Division of the list by that number is O(1) with n processors

Therefore the operation is O(1)

[0]* on a CRCW PRAM https://www.cpp.edu/~gsyoung/CS535/CS535Notes/Part2PRAM.pdf#...

[ Parent | on HN ]

Re:Need Something Sorted? Sleep on It by lupire on Tuesday May 25, 2021 @02:39PM (#27280577)

You're ignoring communication overhead.

[ Parent | on HN ]