סעיף א
פתרו את נוסחת הנסיגה הבאה:
\(T(n) = 2T(n - 1) + 1\)

סעיף ב
תהיינה \(f,g: \mathbb{N} \to \mathbb{R}^+\).
עבור קבוע \(c>0\), נגדיר את היחס \(f(n) = O_c(g(n))\) אם \(f(n) = O(g(n) \log^c(n))\).
הוכיחו או הפריכו:
אם \(f(n) = O_1(g(n))\) וגם \(g(n) = O_1(h(n))\) אז \(f(n) = O_1(h(n))\).
יש להוכיח/להפריך על פי ההגדרה.