Насколько быстро может получиться «нахождение максимума в массиве»?

Этот вопрос возник из дискуссии, которая началась по этому другому вопросу: Распараллелить уже линейный алгоритм . Это не домашнее задание.

Вам предоставляется массив из N номеров и машина с P процессорами и общей памятью CREW (память для одновременного чтения, монопольная запись).

Какова самая точная верхняя граница в самом быстром алгоритме для нахождения наибольшего числа в массиве? [Очевидно, также: что такое сам алгоритм?]

Я не имею в виду общий объем выполненной работы [который никогда не может быть меньше O (N)].