Input: A n^1+1/2 = n^3/2 processor CRCW PRAM, and n integers x₁, … , x_n.

 

Output: The maximum value on the input variables, i.e. x = max{x₁, x₂, …, x_n}.

 

Give a constant time CRCW PRAM algorithm that finds the maximum of n integer variables using n^3/2 processor only (i.e. significantly fewer processors than the algorithm presented in class).

 

Hint: Note that n^1/2 (n^1/2)² = n^3/2.