א. הוכיחו שכל אלגוריתם מבוסס השוואות המחפש ערך נתון בסדרה ממוינת בת \(n\) איברים, מבצע \(\Omega(\log n)\) השוואות במקרה הגרוע.

ב. נניח שבונים ערימת מינימום על ידי הכנסת \(n\) איברים לערימה בזה אחר זה (כלומר על ידי ביצוע \(n\) פעולות Insert). הוכיחו שזמן הריצה הוא \(O(n \log n)\).

ג. הניחו שעומדת לרשותכם 'קופסה שחורה' שמוצאת חציון בזמן לינארי במקרה הגרוע. כתבו אלגוריתם פשוט המתבסס על 'קופסה' זו ומחזיר את האיבר במיקום ה-\(k\) (עבור \(k\) נתון) בזמן לינארי.