מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/נוסחאות נסיגה/תרגילים/נוסחות נסיגה פשוטות/תשובה

1

כרגיל, מותר לנו לקבוע ש$\displaystyle T(10)=k$ עבור קבוע $\displaystyle k$ כלשהו, וזאת משום ש$\displaystyle T(n)$ מתארת את זמן הריצה של אלגוריתם.

נוכיח ש‎‎$\displaystyle T(n)=O(n)$. ליתר דיוק, נוכיח באינדוקציה שקיים $\displaystyle c>0$ כך ש $\displaystyle T(n)\leq c\cdot n$.

הוכחה: (בסיס האינדוקציה) עבור $\displaystyle n=10$, נקבל $\displaystyle T(10)=k\leq c\cdot 10$, כלומר כל שצריך הוא לבחור $\displaystyle c$ המקיים $\displaystyle c\geq k/10$.

(מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל) $\displaystyle n-1$, ונוכיח שהיא נכונה עד (כולל) $\displaystyle n$. מהצבה בנוסחת הנסיגה, נקבל $\displaystyle T(n)=T(n-1)+6\leq c\cdot n-c+6.$
עבור $\displaystyle c\geq 6$, נקבל $\displaystyle T(n)\leq c\cdot n$.

לסיכום, עבור $\displaystyle c\geq \max\{k/10,6\}$, הן בסיס האינדוקציה והן מעבר האינדוקציה מתקיימים.

נוכיח ש‎‎$\displaystyle T(n)=\Omega (n)$. ליתר דיוק, נוכיח באינדוקציה שקיים $\displaystyle c>0$ כך ש $\displaystyle T(n)\geq c\cdot n$.

הוכחה: (בסיס האינדוקציה) עבור $\displaystyle n=10$, נקבל $\displaystyle T(10)=k\geq c\cdot 10$, כלומר כל שצריך הוא לבחור $\displaystyle c$ המקיים $\displaystyle c\leq k/10$.

(מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל) $\displaystyle n-1$, ונוכיח שהיא נכונה עד (כולל) $\displaystyle n$. מהצבה בנוסחת הנסיגה, נקבל $\displaystyle T(n)=T(n-1)+6\geq c\cdot n-c+6.$
עבור $\displaystyle c\leq 6$, נקבל $\displaystyle T(n)\geq c\cdot n$.

לסיכום, עבור $\displaystyle c\leq \min\{k/10,6\}$, הן בסיס האינדוקציה והן מעבר האינדוקציה מתקיימים.

2

עלינו להוכיח שפתרון נוסחת הנסיגה $\displaystyle T(n)=T(n-1)+6\cdot n$ הוא $\displaystyle T(n)=\Theta (n^{2})$. אפשר לעשות זאת בכסעיף הקודם, אך נבחר לעשות זאת (שרירותית) בדדוקציה. נרשום $\displaystyle T(1)=O(1),$
$\displaystyle T(n)=T(n-1)+6\cdot n=T(n-2)+6\cdot (n+n-1)=\ldots =T(1)+6\cdot (n+n-1+\ldots +2)=\Theta (n^{2})$