Minimum time to find the maximum number with multiple processors

Question

For example, suppose there are 32 numbers (not sorted, unknown ranges) and 8 processors, each of which calculates one comparison per minute.

If there is only one processor, then there should be 31 comparisons. But with 8 processors we can compare 16 numbers per minute.

What is the minimum amount of time (in minutes) required to calculate the maximum number? (I worked for about 6 minutes, but I think it can be done in 5, I don’t know how the algorithm works.)

Answer 1

1) 32 numbers -> compare 8 pairs using 8 CPUs -> 24 numbers 2) 24 numbers -> compare 8 pairs using 8 CPUs -> 16 numbers 3) 16 numbers -> compare 8 pairs using 8 CPUs -> 8 numbers 4) 8 numbers -> compare 4 pairs using 4 CPUs -> 4 numbers 5) 4 numbers -> compare all numbers with each other using 6 CPUs (tetrahedron) 

Answer 2

(Edited) 1st 4 steps easy

• compare 8 pairs (16 numbers) → 8 winners1
• compare 8 pairs (16 numbers) → 8 winners2
• compare 8 pairs (8-winner1 vs 8-winners2) → 8 winners,

• compare 4 pairs → 4 winners

  Let's say 4 numbers: a, b, c, d

• compare 6 pairs (a, b) (a, c) (a, d) (b, c) (b, d) (c, d) → The largest number will win 3 times

Answer 3

Think of it as the NCAA bracket, where you let each core handle the game / minute. Throw the logic of the tetrahedron to the last 4, and you will save 1 minute.