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

$\displaystyle T(n)$ מתארת את זמן הריצה של אלגוריתם כלשהו.

1. אנא הוכח שפתרון נוסחת הנסיגה $\displaystyle T(n)=T(n-1)+6$ הוא $\displaystyle T(n)=\Theta (n)$.
2. אנא הוכח שפתרון נוסחת הנסיגה $\displaystyle T(n)=T(n-1)+6\cdot n$ הוא $\displaystyle T(n)=\Theta (n^{2})$.

הנחיות להלן הנחיות לסעיף הראשון: אנא הסבר מדוע מותר לקבוע ש$\displaystyle T(10)=k$ עבור קבוע $\displaystyle k>0$ כלשהו. נניח שקיים קבוע $\displaystyle c>0$ כך שלכל $\displaystyle i<n$ מתקיים ‎$\displaystyle T(i)\leq c\cdot i$. אנא הסבר מדוע בהכרח $\displaystyle T(n)\leq c\cdot (n-1)+6$. אנא מצא תנאי על $\displaystyle c$ כך שבהכרח נובע מכך כי $\displaystyle T(n)\leq c\cdot n$. אנא הסבר מדוע מהאמור עד כה נובע שבהכרח $\displaystyle T(n)=O(n)$. נניח שקיים קבוע $\displaystyle c>0$ כך שלכל $\displaystyle i<n$ מתקיים ‎$\displaystyle T(i)\geq c\cdot i$. אנא הסבר מדוע בהכרח $\displaystyle T(n)\geq c\cdot (n-1)+6$. אנא הסבר מה התנאי על $\displaystyle c$ כך שינבע מכך כי $\displaystyle T(n)\geq c\cdot n$. אנא הסבר מדוע מהאמור עד כה נובע שבהכרח $\displaystyle T(n)=\Omega (n)$. אנא הסבר מדוע מהאמור עד כה נובע שבהכרח $\displaystyle T(n)=\Theta (n)$.