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

שיטה א'

נשתמש באותו הרעיון בו השתמשתנו כדי לנתח טור של לוגריתמים.

ראשית נראה כי $f(n)=O(n^3)$.

כעת נראה כי $f(n)=\mathrm{\Omega }(n^3)$.

שיטה ב'

$f(n)=\sum _{i=1}^n\sum _{j=i}^n[\mathrm{\Theta }(j-i+1)]$.

נשים לב שעבור ערך $i$ כלשהו, נוכל לבצע את החלפת המשתנים $j^{\prime }=j-i$, ונקבל $\sum _{j=i}^n[\mathrm{\Theta }(j-i+1)]=\sum _{j^{\prime }=0}^{n-i}[\mathrm{\Theta }(j^{\prime }+1)]=\sum _{j^{\prime }=0}^{n-i}[\mathrm{\Theta }(j^{\prime })]=\mathrm{\Theta }((n-i{)}^2)$ .

נציב זאת חזרה בסכום הכפול: $f(n)=\sum _{i=1}^n\sum _{j=i}^n[\mathrm{\Theta }(j-i+1)]=\sum _{i=1}^n[(n-i{)}^2]$ .

נבצע החלפת משתנים $i^{\prime }=n-i$, ונקבל:

$f(n)=\sum _{i=1}^n[(n-i{)}^2]=\sum _{i^{\prime }=0}^{n-1}[i{\text{'}}^2]=\mathrm{\Theta }(n^3)$ .