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

נשתמש בפרישה.בעץ המתאים לנוסחה:

1. צומת הראש מציין את $\displaystyle T(n)$, והרמה הראשונה תורמת $\displaystyle \log(n)$.
2. ברמה הבאה, הצומת מציין את $\displaystyle T({\sqrt {n}})=t(n^{1/2})$, והרמה תורמת $\displaystyle \log({\sqrt {n}})=1/2\cdot \log(n)$.
3. ברמה הבאה אחריה, הצומת מציין את $\displaystyle T({\sqrt {n^{1/2}}})=t(n^{1/4})$, והרמה תורמת $\displaystyle \log({\sqrt {n^{1/2}}})=1/4\cdot \log(n)$.

החוקיות איננה מסובכת, ונוכל להוכיח את הטענה הבאה באינדוקציה פשוטה: ברמה ה$\displaystyle i$ (כאשר ראש העץ נחשב ברמה ה0), הצומת מציין את $\displaystyle T(n^{1/2^{i}})$, והרמה תורמת $\displaystyle 1/2^{i}\cdot \log(n)$.

כדי למצוא את גובה העץ, $\displaystyle m$, נפתור $\displaystyle n^{1/2^{i}}=2$: $\displaystyle n^{1/2^{m}}=2$
$\displaystyle \log(n^{1/2^{m}})=1$
$\displaystyle 1/2^{m}\cdot \log(n)=1$
$\displaystyle 2^{m}=\log(n)$
$\displaystyle m=\log(\log(n))$
כאמור, הרמה ה$\displaystyle i$ תורמת $\displaystyle 1/2^{i}\cdot \log(n)$. נותר, לכן, לסכם את $\displaystyle \sum _{i=1}^{\log(\log(n))}[1/2^{i}\cdot \log(n)]$: $\displaystyle \sum _{i=0}^{\log(\log(n))}[1/2^{i}\cdot \log(n)]=$
$\displaystyle \sum _{i=0}^{\log(\log(n))}[1/2^{i}]\cdot \log(n)=$
$\displaystyle \Theta (1)\cdot \log(n)=$
$\displaystyle \Theta (\log(n))$