בכל אופן תראה,יש לך סיגמא מk=1 עד n של k*n
עכשיו בגלל שהn בתוך הסיגמא הוא קבוע, מותר לך להוציא אותו החוצה ולהכפיל אותו בסיגמא שבתוכה יש רק k. עכשיו מה שנשאר לך זה n*sigma(k=1..n) { k }
sigma(k=1..n ) { k } = 1+2+3...+n
עכשיו הסכום הזה שווה לn*(n+1) /2
אז בעצם מה שקיבלת זה n*n*(n+1) /2 = n^3 + n^2
זה ביטוי שחסום מלמטה ע"י n^3 ומלמעלה ע"י 2n^3 ואפשר פורמלית ככה להראות שזה תטא של n^3 (כלומר בסדר גודל של n^3)
אצלינו פשוט הטרמינולוגיה הייתה שונה. אם רצו סדר גודל זה היה כמו להוכיח שמשהו הוא תטא של פונקציה כלשהי, לא יודע מה הכוונה אצליכם.
גירסת הדפסה
סגן המנהל
מפקח
Winner
צל"ש
מומחה
