שאלת מבחן במבני נתונים ומבוא לאלגוריתמים - רקורסיה

נתונה נוסחת הנסיגה הבאה: $$T(n)=49T\!\left(\frac{n}{7}\right)+n^2+n+1$$ פתרו אותה בשיטת **משפט האב**: **א.** זהו $a$, $b$, $f(n)$ וחשבו $n^{\log_b a}$. **ב.** קבעו לאיזה מקרה שייכת הנסיגה. **ג.** כתבו את הפתרון האסימפטוטי.

רמז: זהו: $a=49$, $b=7$, $f(n)=n^2+n+1=\Theta(n^2)$. חשבו $n^{\log_7 49}$.

פתרון: **פרמטרים:** $a=49$, $b=7$, $f(n)=\Theta(n^2)$, $n^{\log_7 49}=n^2$. $f(n)=\Theta(n^{\log_b a})$ → **מקרה 2**: $$\boxed{T(n)=\Theta(n^2\log n)}$$