Algoritma paralel untuk menemukan waktu

Kami disajikan di kelas dengan algoritma untuk menemukan maksimum dalam array secara paralel dalam kompleksitas waktu dengan n 2 komputer.$O(1)$$n^2$

Algoritma itu adalah:

Diberikan array A dengan panjang n:

1. Buat array flag B dengan panjang n dan inisialisasi dengan nol dengan komputer.$n$
2. Bandingkan setiap 2 elemen dan tulis 1 dalam B pada indeks minimum dengan komputer.$n^2$
3. temukan indeks dengan 0 di A dengan komputer.$n$

Dosen menggoda kita itu bisa dilakukan dengan komputer dan dengankompleksitaslognwaktu.$\frac{n}{\log n}$$\log n$

Setelah banyak berpikir saya tidak tahu bagaimana melakukannya. Ada ide?

$n/\log n$$\log n$$\log n$$n/\log n$$\log n$

$n^{1+\epsilon}$$\epsilon > 0$