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

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

1. $\displaystyle f(n)=O(g(n))\Rightarrow g(n)=O(f(n))$
2. $\displaystyle f(n)+g(n)=\Theta (min\{f(n),g(n)\})$
3. $\displaystyle f(n)=O(g(n))\Rightarrow 2^{f(n)}=O(2^{g(n)})$
4. $\displaystyle f(n)+\Theta (f(n))=\Theta (f(n))$
5. $\displaystyle f(n)=2^{\log(n)},g(n)=(\log(n))^{\log(n)}\Rightarrow f(n)=O(g(n))$

כדאי לדעת: משמעות הביטוי בצד שמאל של סעיף 4 הוא הפונקציה $\displaystyle f(n)$ פלוס פונקציה כלשהי ששייכת ל$\displaystyle \Theta (f(n))$.