מציאת נוסחת נסיגה של פונקציה אלגוריתמית

מדעי המחשב ואלקטרוניקה
1

שאלה שהייתה לי במבחן ולא הבנתי אותה אשמח לעזרה שאלמד להבא.

נתונה הפונקציה הבאה:

FuncFoo(n)
    if n=0
        print n
    sum=0
    for i=1 to 2n
        sum=sum+(1/2)
    FuncFoo(lower(sum/3))
    FuncFoo(lower(sum/3))
    FuncFoo(lower(sum/3))

הערה: הפונקציה lower מחזירה ערך תחתון של מספר. למשל מתקיים lower(2.5)=2.

צריך למצוא את נוסחת הנסיגה ולפתור אותה באמצעות שיטת האב או שיטת האיטרציות.

2

הלולאה הראשונה מתבצעת O(n) פעמים, ולכן נקבל T(n)=O(n)+3T(\lfloor n/3 \rfloor).
נבצע איטרציה ונשים לב אינטואיטיבית שמתקיים:

T(n)\in O\left(n+\frac{n}{3}+...+\frac{n}{3^{\log_{3}n}}\right)=O(n)

נוכיח שזה נכון באינדוקציה.
עבור n=1 הלולאה מתבצעת שלוש פעמים מאחר ו-\lfloor 1/3\rfloor = 0, ולכן סיבוכיות הריצה היא O(1).
נניח שהטענה נכונה לכל 1\leq k < n. עבור n נקבל:

T(n)=O(n)+3T\left(\lfloor n/3\rfloor\right)\in O(n) + 3O\left(\lfloor n/3\rfloor\right)=O(n)+3O(n)=O(n)