Assessing Valiant’s Max Algorithm
•The PRAM model caused us to ...
–Exploit the “free use” of read and write collisions, which are not possible in practice
–
–Ignore the costs of data motion, so we adopt an algorithm that runs faster than the time required to bring all data values together, which is W(log n)
–
–So what?