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

נסמן את זמן הריצה של Alg(A, i, j) כ$\displaystyle T(i,j)$.

נצייר את עץ הפרישה של הפונקציה:

מהפרישה אפשר לראות (ולהוכיח פורמלית באינדוקציה), שכל רמה תורמת $\displaystyle \Theta (n)$, והארגומנטים קטנים מרמה לרמה לפי שורש. אם גובה העץ הוא $\displaystyle h$, אז סכום הרמות הוא $\displaystyle \Theta (h\cdot n)$. נותר למצוא את $\displaystyle h$.

נפתור $\displaystyle n^{\frac {1}{2^{h}}}=k$, ונקבל

$\displaystyle {\frac {\log(n)}{2^{h}}}=\log(k)\Rightarrow 2^{h}={\frac {\log(n)}{\log(k)}}\Rightarrow h=\Theta (\log \log(n))$.

הסיבוכיות, לכן, היא $\displaystyle \Theta (n\cdot \log \log(n))$.