א. רינת טענה שכל אלגוריתם מיון מבוסס השוואות, הממיין 5 איברים, חייב לבצע לפחות 10 השוואות במקרה הגרוע, מכיוון שלטענתה \(\lceil \log(5!) \rceil = 10\). האם רינת צודקת? נמקו.
ב. נתון מערך \(A\) בגודל \(n\) של מספרים. יש לתאר אלגוריתם, בסיבוכיות זמן של \(O(n \log n)\), המחזיר אינדקסים (מבוססי 1) של שני איברים שונים שסכומם הוא כפליים חציון המערך. אם לא קיימים שני אינדקסים כאלה, האלגוריתם יחזיר -1.
החציון של מערך בגודל \(n\) מוגדר כאיבר במיקום ה-\(\lceil n/2 \rceil\) במערך הממוין.
לדוגמה, עבור המערך \(A=[7,3,6,8,1,5]\), האלגוריתם יחזיר את האינדקסים 1 ו-2. החציון של \(A\) הוא 5 (האיבר השלישי במערך הממוין \([1,3,5,6,7,8]\)), ומתקיים \(A[1]+A[2]=7+3=10=2 \times 5\).