א. פתרו את נוסחת הנסיגה:

\[\begin{cases} T(1) = c > 0 \\ T(n) = 16T(n/4) + n^a \cdot \log^{a+1} n \end{cases} \]

\(a\) הוא פרמטר ממשי חיובי.

ב. נתונות הפונקציות:
\(g(n) = 2^{\log_2 n}\)
\(f(n) = \sum_{i=1}^{n^2} \log i\)
קבעו אילו מהיחסים האסימפטוטיים מתקיימים בין \(f\) ל-\(g\).

ג. תנו דוגמה לשני זוגות של פונקציות (חיוביות, עולות, לא חסומות) \((f,g)\), כך שעבור שני הזוגות יתקיים \(f=O(g)\), אבל לאחד הזוגות יתקיים \(g \circ f = o(f \circ g)\), ואילו לזוג השני יתקיים \(g \circ f = \Theta(f \circ g)\).
תזכורת: \(g \circ f\) היא הרכבה של \(g\) על \(f\) כלומר הפונקציה \([g(f(n))]\).