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

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

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

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

לכן:

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

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

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