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

ההוכחה דומה למדי ל[[מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/סדרי גדילה#אדיטיביות|הוכחת האדיטיביות שראינו בהרצאה]]:

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

*<math dir = "ltr">\displaystyle f_1(n) = \Omega(f(n))</math> משמעו שלכל <math dir = "ltr">\displaystyle n \ge n_{0,f}</math>,‏     <math dir = "ltr">\displaystyle f_1(n) \ge c _f\cdot f(n)</math>,‏ עבור <math dir = "ltr">\displaystyle c_f, n_{0, f} > 0</math> כלשהם.
*<math dir = "ltr">\displaystyle g_1(n) = \Omega(g(n))</math> משמעו שלכל<math dir = "ltr">\displaystyle n \ge n_{0,g}</math>,‏     <math dir = "ltr">\displaystyle g_1(n) \ge _g\cdot g(n)</math>,‏ עבור <math dir = "ltr">\displaystyle c_g, n_{0, g}     > 0</math> כלשהם.
לכן:
*לכל <math dir = "ltr">\displaystyle n \ge \max\{n_{0,f}, n_{0,g}\}</math>,‏ <math dir = "ltr">\displaystyle f_1(n) \ge   \max\{c_f, c_g\}\cdot f(n)</math>.
*לכל <math dir = "ltr">\displaystyle n \ge \max\{n_{0,f}, n_{0,g}\}</math>,‏ <math dir = "ltr">\displaystyle g_1(n) \ge   \max\{c_f, c_g\}\cdot g(n)</math>.

מקבלים את התוצאה ע"י חיבור שני האי-שוויונים האחרונים.}}
[[קטגוריה:מבני נתונים ואלגוריתמים]]