חישוב זמן ריצה

[loresin1]

חישוב זמן ריצה

שלום,

השאלה הנ"ל היא מתחום מדעי המחשב, אך מכיוון שכל מה שלא הבנתי כאן הוא חישוב זמן הריצה- מקווה שמתאים לשאול כאן.

ממה שרשום בפתרון כאן, מספר הקריאות לפונקציה הרקורסיבית הראשונה הוא לכל היותר m, וכנ"ל לגבי השנייה.
ומדוע זה ככה? אני פשוט לא מצליח לראות את זה...

 

[israelmiv]

אפשר לראות את זה כך:

בכל קריאה לפונקציה print-bigger הערך של i יהיה שונה. i מסוים יופיע באחת הקריאות רק אם אבא שלו גדול או שווה לx. כעת השאלה היא כמה i כאלה יש?
יש m אברים גדולים או שווים לx, ויש להם לכל היותר 2m בנים. תוסיף לזה את השורש שקוראים לו בפעם הראשונה.

 

[loresin1]

אחלה הסבר- תודה!