א. נתון מערך \(A[1..n]\) המקיים את התנאי: אם \(i < j\) וגם \(A[i] > A[j]\), אז \(j=i+1\).
(\(1 \le i, j \le n\))

איזה אלגוריתם ימיין את \(A\) בזמן טוב יותר: מיון-הכנסה או מיון-מיזוג? הוכיחו את טענתכם.

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

ג. נתון תור קדימויות \(P\) שבאמצעותו ניתן לבצע את שתי הפעולות INSERT (הכנסת איבר) ו-EXTRACT-MAX (מחיקת המקסימום). לא נתון כיצד תור זה ממומש.
הוכיחו שחייבת להיות לפחות סדרה אחת של \(m\) פעולות INSERT ו-EXTRACT-MAX (בסדר כלשהו), כך שלפחות אחת הפעולות מתבצעת בזמן \(\Omega(\log m)\).

הערה: אין קשר בין הסעיפים השונים.