3 ms·
With a linear time O(N) first pass you can identify the minimum element in the list. This reduces M from being the largest element to being the difference betwe
by BearsAreCool 5y ago
With a linear time O(N) first pass you can identify the minimum element in the list. This reduces M from being the largest element to being the difference between the largest and the smallest element.
- rileymat2 5y agoIf 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!
- david_allison 5y agoLet'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#page=1 https://www.cpp.edu/~gsyoung/CS535/CS535Notes/Part2PRAM.pdf#...
- lupire 5y agoYou're ignoring communication overhead.