סעיף א': חלוקת מערך לשני חלקים
נתון מערך \(A\) בגודל \(n\). הצע אלגוריתם המחלק את איברי המערך לשתי קבוצות זרות, \(A_1\) ו-\(A_2\), כך שכל איבר ב-\(A_1\) קטן או שווה לכל איבר ב-\(A_2\). גודלי הקבוצות צריכים להיות \(\lfloor n/2 \rfloor\) ו-\(\lceil n/2 \rceil\). מהי סיבוכיות הזמן של האלגוריתם שהצעת?

סעיף ב': ניתוח נוסחאות נסיגה
פתור את נוסחאות הנסיגה הבאות וקבע את הסיבוכיות שלהן במונחי \(\Theta\). הנח כי \(T(1) = \Theta(1)\).

1. \(T(n) = T(n/2) + cn\)
2. \(T(n) = T(n/2) + c n \log n\)
3. \(T(n) = 2T(n/2) + O(n)\)
4. \(T(n) = T(2n/3) + O(1)\)
5. \(T(n) = T(2n/3) + O(n)\)