How fast can 'finding the max in an array' possibly get?

Question

This question comes from a discussion that was touched off on this other question: Parallelize already linear-time algorithm. It is not homework.

You are given an array of N numbers, and a machine with P processors and a shared CREW memory (Concurrent Read, Exclusive Write memory).

What is the tightest upper bound on the fastest algorithm to find the largest number in the array? [Obviously, also: What is the algorithm itself?]

I am not referring to the total amount of work performed [which can never be less than O(N)].

Answer 1

I think it's O(N/P') + O(Log2(P')), where P'=min{N,P}. P' processors search for max of N/P' elements each, followed by Log2 pairwise merges done in parallel. The first P'/2 merges are done by even-numbered processors, next 'P'/4' - by processors at locations divisible by 8, then by 16, and so on.

Edit P' is introduced to cover the case when you have significantly more processor nodes than the elements that you need to search.

Answer 2

Cook, Dwork, and Reischuk showed that any CREW algorithm for finding the maximum of n elements must run in Omega(lg n) time, even with an unlimited number of processors and unlimited memory. If I remember correctly, an algorithm with a matching upper bound appears in their paper:

Stephen Cook, Cynthia Dwork, and Rüdiger Reischuk. Upper and lower time bounds for parallel random access machines without simultaneous writes. SIAM Journal on Computing, 15(1):87-97, 1986.