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

(לתזכורת, $\displaystyle f(n),g(n)$ הן פונקציות חיוביות ממש.)

1. לא נכון. נפריך ע"י $\displaystyle f(n)=n^{2},g(n)=n^{3}$.
2. לא נכון. נפריך ע"י $\displaystyle f(n)=n^{2},g(n)=n^{3}$.
3. לא נכון. נפריך ע"י $\displaystyle f(n)=2\cdot n,g(n)=n$.
4. לכל פונקציה $\displaystyle g(n)=\Theta (f(n))$ מתקיים ש$\displaystyle c''\cdot f(n)\leq g(n)\leq c'\cdot f(n)$, עבור $\displaystyle c'',c'>0$ כלשהם, החל מ$\displaystyle n_{0}>0$ כלשהו. לכן, החל מאותו $\displaystyle n_{0}$,‏‏ $\displaystyle (1+c'')\cdot f(n)\leq f(n)+g(n)\leq (1+c')\cdot f(n),$
   ‏ מה שמוכיח את הטענה.
5. $\displaystyle lim_{n\rightarrow \infty }[f(n)/g(n)]=0$ (לפי כללים פשוטים מחדו"א),

ולכן עפ"י כללי הגבולות שראינו, הטענה נכונה.