حل سوالهای باقیمانده از نمونه سوالهای پردازش موازی

سوالی که ماکسیمم را در مدل CRCW می‌خواست: n^2 پردازنده داریم که هر کدام مقدار i ام و j ام را مقایسه می‌کند و اگر اولی کمتر بود درایه‌ی متناظر آن را صفر می‌کند. عنصری که درایه‌ی متناظر آن ۱ است جواب است. می‌توانیم فرض کنیم مرحله بعد n پردازنده بیت متناظر را می‌خوانند و اگر ۱ بود جواب را در محل جواب می‌نویسند. که کل این کار O(1) زمان می‌برد.

سوال بعدی در مورد این بود که الگوریتمی داده شده بود و قرار بود ثابت کنیم 2n/p عنصر حداکثر عناصر هر پردازنده خواهد بود. دلیل آن این است که هر کدام از جداکننده‌های اولیه n/p2 عنصر را جدا می‌کردند و می‌دانیم در بدترین حالت می‌تواند جداکننده نهایی طوری با بقیه اختلاف داشته باشد که قبل از میانه بعدی باشد اما همه‌ی عددهای بین را شامل شود. در این حالت p*n/p2 عنصر بیشتر از کران پایین (که n/p است) داریم پس حداکثر تعداد عناصر 2n/p می‌شود.