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

ההוכחה דומה למדי להוכחת האדיטיביות שראינו בהרצאה:

הוכחה: (1) עפ"י ההגדרה:

• $\displaystyle f_{1}(n)=\Omega (f(n))$ משמעו שלכל $\displaystyle n\geq n_{0,f}$,‏ $\displaystyle f_{1}(n)\geq c_{f}\cdot f(n)$,‏ עבור $\displaystyle c_{f},n_{0,f}>0$ כלשהם.
• $\displaystyle g_{1}(n)=\Omega (g(n))$ משמעו שלכל$\displaystyle n\geq n_{0,g}$,‏ $\displaystyle g_{1}(n)\geq _{g}\cdot g(n)$,‏ עבור $\displaystyle c_{g},n_{0,g}>0$ כלשהם.

לכן:

• לכל $\displaystyle n\geq \max\{n_{0,f},n_{0,g}\}$,‏ $\displaystyle f_{1}(n)\geq \max\{c_{f},c_{g}\}\cdot f(n)$.
• לכל $\displaystyle n\geq \max\{n_{0,f},n_{0,g}\}$,‏ $\displaystyle g_{1}(n)\geq \max\{c_{f},c_{g}\}\cdot g(n)$.

מקבלים את התוצאה ע"י חיבור שני האי-שוויונים האחרונים.