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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי

1[עריכה]

כרגיל, מותר לנו לקבוע ש עבור קבוע כלשהו, וזאת משום ש מתארת את זמן הריצה של אלגוריתם.


נוכיח ש‎‎. ליתר דיוק, נוכיח באינדוקציה שקיים כך ש .


הוכחה: (בסיס האינדוקציה) עבור , נקבל , כלומר כל שצריך הוא לבחור המקיים .

(מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל) , ונוכיח שהיא נכונה עד (כולל) . מהצבה בנוסחת הנסיגה, נקבל
עבור , נקבל .


לסיכום, עבור , הן בסיס האינדוקציה והן מעבר האינדוקציה מתקיימים.

נוכיח ש‎‎. ליתר דיוק, נוכיח באינדוקציה שקיים כך ש .


הוכחה: (בסיס האינדוקציה) עבור , נקבל , כלומר כל שצריך הוא לבחור המקיים .

(מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל) , ונוכיח שהיא נכונה עד (כולל) . מהצבה בנוסחת הנסיגה, נקבל
עבור , נקבל .


לסיכום, עבור , הן בסיס האינדוקציה והן מעבר האינדוקציה מתקיימים.

2[עריכה]

עלינו להוכיח שפתרון נוסחת הנסיגה הוא . אפשר לעשות זאת בכסעיף הקודם, אך נבחר לעשות זאת (שרירותית) בדדוקציה. נרשום