כרגיל, מותר לנו לקבוע ש
עבור קבוע
כלשהו, וזאת משום ש
מתארת את זמן הריצה של אלגוריתם.
נוכיח ש
. ליתר דיוק, נוכיח באינדוקציה שקיים
כך ש
.
הוכחה: (בסיס האינדוקציה) עבור
, נקבל
, כלומר כל שצריך הוא לבחור
המקיים
.
(מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל)
, ונוכיח שהיא נכונה עד (כולל)
. מהצבה בנוסחת הנסיגה, נקבל ![{\displaystyle \displaystyle T(n)=T(n-1)+6\leq c\cdot n-c+6.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/53e7cfca85a74f0f7cd2e2dadf4b6a5096a21e87)
עבור
, נקבל
.
לסיכום, עבור
, הן בסיס האינדוקציה והן מעבר האינדוקציה מתקיימים.
נוכיח ש
. ליתר דיוק, נוכיח באינדוקציה שקיים
כך ש
.
הוכחה: (בסיס האינדוקציה) עבור
, נקבל
, כלומר כל שצריך הוא לבחור
המקיים
.
(מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל)
, ונוכיח שהיא נכונה עד (כולל)
. מהצבה בנוסחת הנסיגה, נקבל ![{\displaystyle \displaystyle T(n)=T(n-1)+6\geq c\cdot n-c+6.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cf10f4c319d0ff484ac6b388fec311e2ce8fbb81)
עבור
, נקבל
.
לסיכום, עבור
, הן בסיס האינדוקציה והן מעבר האינדוקציה מתקיימים.
עלינו להוכיח שפתרון נוסחת הנסיגה
הוא
. אפשר לעשות זאת בכסעיף הקודם, אך נבחר לעשות זאת (שרירותית) בדדוקציה. נרשום ![{\displaystyle \displaystyle T(1)=O(1),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c90c1a4d55d1f1f6ee4bfeb25ef4b67bd0d08da)
![{\displaystyle \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})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d3ebb041fa9e7de8e08504b47445ed3fa93e085)