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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

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


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

  • משמעו שלכל ,‏ ,‏ עבור כלשהם.
  • משמעו שלכל,‏ ,‏ עבור כלשהם.

לכן:

  • לכל ,‏ .
  • לכל ,‏ .

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

מש"ל.PNG