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

נשתמש בעץ פרישה. ברמה הראשונה יש צומת יחיד, והוא תורם $\displaystyle f(n)$. ברמה השניה יש $\displaystyle a$ צמתים, וכל אחד מהם תורם $\displaystyle f\left({\frac {n}{b}}\right)$. ברמה ה$\displaystyle i$ (בהנחה שהרמה הראשונה היא ב$\displaystyle i=0$), יש $\displaystyle a^{i}$ צמתים, וכל אחד מהם תורם $\displaystyle f\left({\frac {n}{b^{i}}}\right)$. אנו יודעים שגובה העץ הוא $\displaystyle h=\Theta (\log _{b}(n))$. נפשט: $\displaystyle \sum _{i=0}^{h}\left[a^{i}\cdot f\left({\frac {n}{b^{i}}}\right)\right]=$
$\displaystyle \sum _{i=0}^{h}\left[a^{i}\cdot \Theta \left(\left({\frac {n}{b^{i}}}\right)^{\log _{b}(a)}\cdot \log ^{k}\left({\frac {n}{b^{i}}}\right)\right)\right]=$
$\displaystyle \Theta \left(\sum _{i=0}^{h}\left[a^{i}\cdot {\frac {n^{\log _{b}(a)}}{b^{i\cdot \log _{b}(a)}}}\cdot \log ^{k}\left({\frac {n}{b^{i}}}\right)\right]\right)=$
$\displaystyle \Theta \left(\sum _{i=0}^{h}\left[a^{i}\cdot {\frac {n^{\log _{b}(a)}}{a^{i}}}\cdot \log ^{k}\left({\frac {n}{b^{i}}}\right)\right]\right)=$
$\displaystyle \Theta \left(n^{\log _{b}(a)}\sum _{i=0}^{h}\left[\cdot \log ^{k}\left({\frac {n}{b^{i}}}\right)\right]\right)=$
$\displaystyle \Theta \left(n^{\log _{b}(a)}\sum _{i=0}^{h}\left[\left(\log(n)-i\cdot \log(b)\right)^{k}\right]\right)=$
$\displaystyle \Theta \left(n^{\log _{b}(a)}\log(b)^{k}\sum _{i=0}^{h}\left[\left({\frac {\log(n)}{\log(b)}}-i\right)^{k}\right]\right)$
נשים לב שעפ"י חסמי האינטגרלים לטורים,‏ $\displaystyle \sum _{i=0}^{h}\left[\left({\frac {\log(n)}{\log(b)}}-i\right)^{k}\right]=\Theta \left(\log ^{k+1}(n)\right)$.