سوال ۷۰ کنکور ارشد مهندسی کامپیوتر ۱۴۰۱

آرایه A شامل n عنصر داده شده است. عنصری از آرایه که حافظ بیش از $\frac{n}{2}$ بار تکرار شده باشد را یک عضو پرتکرار می‌نامیم. می‌خواهیم در آرایه A یک عضو پرتکرار را در صورت وجود پیدا کنیم. در این کار از یک روش تقسیم و غلبه به این صورت استفاده می‌کنیم: ابتدا آرایه را به دو قسمت با اندازه برابر تقسیم می‌کنیم و در هر کدام از قسمت‌ها به طور بازگشتی عضو پرتکرار را در صورت وجود پیدا می‌کنیم. سپس میزان تکرار هر عضو پرتکرار را که از دو نیمه آرایه به دست آمده باشد، در آرایه A جستجو می‌کنیم و در صورتی که از هر دو نیمه آرایه به دست آمده باشد آن را به‌عنوان عضو پرتکرار آرایه A انتخاب می‌کنیم. کدام گزینه در خصوص این الگوریتم درست است؟ (فرض کنید n توانی از ۲ است.)