נתונה השאלה הבאה, המחולקת לשלושה סעיפים:

א) הפרדת איברים עוקבים ב-SELECT
האם הטענה הבאה נכונה? נמקו.
באלגוריתם SELECT למציאת האיבר ה-\(k\)-י בגודלו, האיברים ה-\(k\)-י וה-\((k-1)\)-י בגודלם לעולם לא יימצאו באותו צד של איבר הציר (pivot) לאחר הפעלת PARTITION.

ב) מציאת האיברים \(k\) ו-\((k-1)\)
הצע אלגוריתם בסיבוכיות זמן ריצה של \(O(n)\) למציאת האיבר ה-\(k\)-י בגודלו והאיבר ה-\((k-1)\)-י בגודלו במערך של \(n\) איברים. נתחו את סיבוכיות הזמן של האלגוריתם שהצעתם.

ג) אלטרנטיבה עם ערימה
הצע אלגוריתם חלופי המבוסס על ערימה למציאת שני האיברים הללו. נתחו את סיבוכיותו וקבעו מתי אלגוריתם זה יהיה יעיל יותר מהאלגוריתם שהצעתם בסעיף ב'.