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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

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

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

עץ הפרישה. ט"ו בשבט שמח.

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

נפתור , ונקבל

.


הסיבוכיות, לכן, היא .