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

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

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

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

לכן:

• לכל $n\ge \max \{n_{0,f},n_{0,g}\}$,‏ $f(n)\ge c_f\cdot f(n)$.
• לכל $n\ge \max \{n_{0,f},n_{0,g}\}$,‏ $g(n)\ge c_g\cdot g(n)$.

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

• לכל $n\ge \max \{n_{0,f},n_{0,g}\}$,‏‏ $f(n)\ge c_f\cdot c_g\cdot h(n)$.