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

אנא מצא חסמים עליונים ותחתונים (כלומר, מסוג $\displaystyle \Omega$ ו$\displaystyle O$) טובים ככל האפשר לפונקציה $\displaystyle T(n)$ בכל אחד מהסעיפים הבאים. ($\displaystyle T(n)$ מתארת את זמן הריצה של אלגוריתם כלשהו.)

1. $\displaystyle T(n)=3\cdot T(n/2)+n\cdot \log(n)$.‏
2. $\displaystyle T(n)=T(n-1)+\log(n)$.‏
3. $\displaystyle T(n)=T(\alpha \cdot n)+T((1-\alpha )\cdot n)+\Theta (n)$, כאשר $\displaystyle 0<\alpha <1$ הוא קבוע כלשהו.‏