מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/עצי חיפוש בינריים/תרגילים/זמן הריצה של הפונקציות למעבר על כל הצמתים/תשובה

עלינו להראות שיש שני קבועים, $\displaystyle c_{0}$ ו$\displaystyle c_{1}$ המקיימים $\displaystyle c_{1}\cdot n\leq T(n)\leq c_{0}\cdot n$ עבור ערכי $\displaystyle n$ גדולים מספיק.

הטענה שקיים $\displaystyle c_{1}$ $\displaystyle T(n)\geq c_{1}\cdot n$ (כלומר $\displaystyle T(n)=\Omega (n)$) ברורה, מפני שאנו יודעים שהפונקציה עוברת על כל אחד מהצמתים, ויש $\displaystyle n$ צמתים עפ"י ההגדרה. נוכיח לכן רק את הטענה לגבי קיומו של $\displaystyle c_{0}$.

הוכחה: (בסיס האינדוקציה) נבחר את בסיס האינדוקציה כ$\displaystyle n=1$.

ונסמן ב$\displaystyle k$ את זמן הריצה של הפונקציה על קלט בגודל 1. מכאן נקבל את האילוץ על $\displaystyle c_{0}$: $\displaystyle k\leq c_{0}\cdot 1=c_{0}$. בוודאי שקיים $\displaystyle c_{0}$ המקיים אילוץ זה.

(מעבר האינדוקציה) נניח שהטענה מתקיימת לכל $\displaystyle n'<n$.

נזכר שראינו כבר את נוסחת הנסיגה המתאימה לבעיה $\displaystyle T(n)=T(n')+O(1)+T(n-n'-1)$ (קל לראות זאת גם מהתרשים הבא).

מעבר האינדוקציה.

הנוסחה אומרת שקיים $\displaystyle k'$ כך שמתקיים $\displaystyle T(n)\leq T(n')+k'+T(n-n'-1)$.

נשתמש בנוסחת הנסיגה ובהנחת האינדוקציה, ונקבל

$\displaystyle T(n)\leq T(n')+k'+T(n-n'-1)\leq$
$\displaystyle c_{0}\cdot n'+k'+c_{0}(n-n'-1)=$
$\displaystyle c_{0}\cdot n+(k'-c_{0})$

אם נבחר $\displaystyle k'\leq c_{0}$ אז $\displaystyle (k'-c_{0})$ שלילי, ולכן בהכרח $\displaystyle T(n)\leq c_{0}\cdot n$.

נשים לב שבסיס האינדוקציה הגביל אותנו לבחור $\displaystyle k\leq c_{0}$, ומעבר האינדוקציה הגביל אותנו לבחור $\displaystyle k'\leq c_{0}$.

מכאן יוצא שאכן יש $\displaystyle c_{0}$ המתאים לבעיה (למעשה יש אינסוף כאלה) - עלינו פשוט לבחור $\displaystyle c_{0}$ המקיים

$\displaystyle c_{0}\geq \max \left\{k,k'\right\}$.