מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/מציאת סיבוכיות פסוודו-קוד/תרגילים/קריאות רקרורסיביות בלולאת קפיצות שורש/תשובה
קפיצה לניווט
קפיצה לחיפוש
נסמן את זמן הריצה של Alg(A, i, j)
כ.
נצייר את עץ הפרישה של הפונקציה:
מהפרישה אפשר לראות (ולהוכיח פורמלית באינדוקציה), שכל רמה תורמת , והארגומנטים קטנים מרמה לרמה לפי שורש. אם גובה העץ הוא , אז סכום הרמות הוא . נותר למצוא את .
נפתור , ונקבל
.
הסיבוכיות, לכן, היא
.