- הגשות
- פתרונות
- פתרון רשמי
- תיאור
א. פתרו את נוסחת הנסיגה הבאה:
\(T(n) = 5T(n / 2) + n^2+n+\sqrt{n}\)
ב. הוכיחו ישירות לפי ההגדרה, עבור כל שלוש פונקציות חיוביות \(f, g, h\) מהמספרים הטבעיים למספרים הטבעיים:
אם \(f(n) = \Omega(g(n))\) וגם \(g(n) = \Omega(h(n))\), אז \(f(n) = \Omega(h(n))\).
בסעיף א', השתמשו במשפט המאסטר. בסעיף ב', היזכרו בהגדרה הפורמלית של סימון \(\Omega\) והרכיבו את אי-השוויונים.