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

כבר ראינו את נוסחת הנסיגה $\displaystyle T(n)=\sum _{i=0}^{n-1}[T(i)\cdot T(n-i-1)]$. נשתמש בזאת כדי להוכיח את הטענה בשאלה באינדוקציה. נראה שקיים $\displaystyle c>0$ כך שתמיד $\displaystyle T(n)\geq c\cdot 2^{n}$.

הוכחה: (מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל) $\displaystyle n-1$, ונראה שהיא נכונה גם ל$\displaystyle n$.

$\displaystyle T(n)=\sum _{i=0}^{n-1}[T(i)\cdot T(n-i-1)]\geq$
$\displaystyle \sum _{i=0}^{n-1}[c\cdot 2^{i}\cdot c\cdot 2^{n-i-1}]=$
$\displaystyle {\frac {c^{2}}{2}}\sum _{i=0}^{n-1}[2^{n}]=$
$\displaystyle {\frac {n\cdot c}{2}}c\cdot 2^{n}$

נפתור $\displaystyle {\frac {n\cdot c}{2}}\geq 1$, ונקבל $\displaystyle c\geq {\frac {2}{n}}$. עבור $\displaystyle n\geq 5$, נקבל שמספיק שיתקיים $\displaystyle c\geq {\frac {2}{5}}$.

מבדיקת מספר העצים השונים, עולה שקיים $\displaystyle c$ מתאים גם לבסיס האינדוקציה (המקרים $\displaystyle n\leq 4$).