תרגול 3 - Asymptotic Analysis & Recurrence

1. רקע

2. תרגיל 1: \(f(n) = n \log(n^5) + 6n\) — \(O(n \log n)\) ו-\(\neq O(n)\)

חלק 1 — \(f(n) = O(n \log n)\)

לכל n ≥ 2:
f(n) = n·log(n⁵) + 6n = 5n·log(n) + 6n
     ≤ 5n·log(n) + 6n·log(n)         [כי log(n) ≥ 1 כשn ≥ 2]
     = 11n·log(n).
לכן עבור n₀ = 2 ו-c = 11, f(n) ≤ c·n log n. ✓

חלק 2 — \(f(n) \neq O(n)\)

בדרך השלילה: נניח שיש c > 0, n₀ עם f(n) ≤ cn לכל n > n₀.
אז בפרט n·log(n) ≤ f(n) ≤ cn ⟹ log(n) ≤ c.
אבל log(n) בלתי חסום! ניקח N = max(n₀, 2^c) + 1.
אזי N > n₀ ו-log(N) > c, כלומר f(N) > cN. סתירה. ∎

3. תרגיל 2: \(2^n \in \Omega(3^{\sqrt{n}})\)

נח לעבור ללוגריתמים. שימו לב: 4 > (log₂ 3)² (כי log₂ 3 ≈ 1.585, 1.585² ≈ 2.51 < 4).
לכן לכל n ≥ 4:    √n ≥ 2 ≥ log₂ 3.

log(f(n)) = log(2ⁿ) = n = √n · √n ≥ √n · log 3 = log(3^√n).

מכיוון שפונקציית הלוג מונוטונית עולה: f(n) ≥ 3^√n.

לכן עבור n₀ = 4, c = 1, מתקיים f(n) ≥ c·3^√n. ⟹ 2ⁿ ∈ Ω(3^√n). ∎

4. תרגיל 3: \(\log(n!) \in \Theta(n \log n)\)

חסם עליון \(\log(n!) = O(n \log n)\)

log(n!) = ∑_{i=1}^{n} log(i) ≤ ∑_{i=1}^{n} log(n) = n·log(n).
n₀ = 2, c = 1 עובד.

חסם תחתון \(\log(n!) = \Omega(n \log n)\)

log(n!) = ∑_{i=1}^{n} log(i) ≥ ∑_{i=n/2}^{n} log(i)
                              ≥ (n/2)·log(n/2)
                              = (1/2)·n log(n) − (1/2)·n log(2)
                              ≥ (1/4)·n log(n)         [לכל n > 4]

n₀ = 4, c = 1/4 עובד. ✓

⟹ log(n!) ∈ Θ(n log n). ∎

5. תרגיל 4: T/F — לכל f, g, מתקיים f=O(g) או g=O(f)?

הפרכה

דוגמה נגדית:
  f(n) = n
  g(n) = { n²  אם n זוגי
        { 1   אם n אי-זוגי }

• f ≠ O(g): עבור n אי-זוגי, g(n)=1 ו-f(n)=n. אין c קבוע כך ש-n ≤ c לכל n אי-זוגי גדול.
• g ≠ O(f): עבור n זוגי, g(n)=n² ו-f(n)=n. אין c עם n² ≤ c·n לכל n זוגי גדול.

⟹ הטענה אינה נכונה. ∎

6. תרגיל 5: ניתוח קוד רקורסיבי

My_algorithm(n)
  If n > 1 then
    For i from 1 to n-1:
      Do_something()    // O(1)
    m = floor(n / 2)
    My_algorithm(m)

1) נוסחה רקורסיבית

הניתוח שורה-שורה:

• If: O(1)
• For loop של (n-1) קריאות O(1): O(n)
• floor: O(1)
• קריאה רקורסיבית עם m=n/2: T(n/2)

2) פתרון בהצבה חוזרת

T(n) ≤ T(n/2) + c₂n
     ≤ T(n/4) + c₂(n/2) + c₂n
     ≤ T(n/8) + c₂(n/4) + c₂(n/2) + c₂n
     ...
     ≤ T(n/2ᵏ) + c₂ · ∑_{i=0}^{k-1} n/2ⁱ

מתי הבסיס? n/2ᵏ = 1 ⟹ k = log₂ n.

T(n) ≤ T(1) + c₂·n·∑_{i=0}^{∞}(1/2)ⁱ ≤ c₁ + 2c₂n = O(n).

אישור באינדוקציה

נוכיח: ∃c > 0 כך שלכל n ≥ 1, T(n) ≤ c·n. נבחר c = max(c₁, 2c₂).

• בסיס n=1: T(1) = c₁ ≤ max(c₁, 2c₂) = c. ✓
• הנחה: לכל k < n, T(k) ≤ ck.
• צעד: T(n) ≤ T(n/2) + c₂n ≤₁ c·(n/2) + c₂n = (cn + 2c₂n)/2 ≤₂ (cn + cn)/2 = cn. ✓
  (השלב ≤₁ — הנחת אינדוקציה. ≤₂ — מתקיים כי c ≥ 2c₂ ⟹ 2c₂n ≤ cn.)

7. תרגיל 6: T/F — קיימות f, g עם g(n) < f(n) לכל n>0 ו-f = O(g)?

נכון! דוגמה:
  f(n) = 2n + 1, g(n) = n.

• g < f: לכל n > 0, n < 2n + 1. ✓
• f = O(g): 2n + 1 ≤ 3n לכל n ≥ 1, לכן f(n) ≤ 3·g(n) ⟹ f = O(n). ✓

8. תרגיל 7 (מועד א' 2022)

נכון. ההוכחה:

(1) תמיד T_W(n) ≥ T_A(n)   [מהגדרת ממוצע ≤ הכי גרוע].

(2) T_A ∈ Θ(n² log n) ⟹ ∃c > 0, n₀ כך שלכל n ≥ n₀,
    T_A(n) ≥ c · n² log n.

(3) שילוב (1)+(2):
    T_W(n) ≥ T_A(n) ≥ c · n² log n.

(4) n² ≥ n לכל n ≥ 1, לכן:
    T_W(n) ≥ c · n² log n ≥ c · n log n.

⟹ T_W(n) ∈ Ω(n log n) (אותו c, אותו n₀). ∎

9. דף עזר