שאלת מבחן במבוא למדעי המחשב - אוניברסיטת בר-אילן 2024 - סיבוכיות זמן

מה הסיבוכיות (ב-$\Theta$) של הנוסחה הבאה: $$T(n) = 2T(n-1) + \left(\frac{1}{2}\right)^n$$ כאשר $T(1) = 1$. ניתן להשתמש בעץ ריקורסיה, שיטת המסטר, או בכל שיטה אחרת הנראית מתאימה, אך הראו את דרך הפתרון.

רמז: זו נוסחת נסיגה לינארית (לא מתאימה ל-Master Theorem). פתחו את הנוסחה ע"י הצבה חוזרת: $T(n) = 2^k T(n-k) + \sum$. הביטוי $(1/2)^n$ קטן מאוד ולא משמעותי — הגורם הדומיננטי הוא $2^{n-1} \cdot T(1)$.

פתרון: **פתיחה ע"י הצבה חוזרת:** $$T(n) = 2T(n-1) + (1/2)^n$$ $$= 2[2T(n-2) + (1/2)^{n-1}] + (1/2)^n$$ $$= 4T(n-2) + 2 \cdot (1/2)^{n-1} + (1/2)^n$$ $$= 2^k T(n-k) + \sum_{j=0}^{k-1} 2^j \cdot (1/2)^{n-j}$$ ב-$k = n-1$: $$T(n) = 2^{n-1} \cdot T(1) + \sum_{j=0}^{n-2} 2^j \cdot (1/2)^{n-j}$$ $$= 2^{n-1} + \sum_{j=0}^{n-2} \frac{2^j}{2^{n-j}} = 2^{n-1} + \sum_{j=0}^{n-2} \frac{4^j}{2^n}$$ $$= 2^{n-1} + \frac{1}{2^n} \cdot \frac{4^{n-1} - 1}{3}$$ $$= 2^{n-1} + \frac{2^{2n-2} - 1}{3 \cdot 2^n} = 2^{n-1} + \frac{2^{n-2}}{3} - \frac{1}{3 \cdot 2^n}$$ הגורם הדומיננטי הוא $2^{n-1}$. $$\boxed{T(n) = \Theta(2^n)}$$ $\blacksquare$