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

שיטה א'

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

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

הוכחה: $\displaystyle f(n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]\leq \sum _{i=1}^{n}\sum _{j=1}^{n}[\Theta (n)]=\Theta (n^{3})$
.

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

הוכחה: $\displaystyle f(n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]\geq \sum _{i=1}^{n/4}\sum _{j=i}^{n}[\Theta (j-i+1)]\geq \sum _{i=1}^{n/4}\sum _{j=3n/4}^{n}[\Theta (j-i+1)]$.
נשים לב שכאשר $\displaystyle i$ בתחום $\displaystyle 1,\ldots ,n/4$ ו$\displaystyle j$ בתחום $\displaystyle 3n/4,\ldots ,n$, אז $\displaystyle \Theta (j-i+1)=\Omega (n/2)=\Omega (n)$.

לכן נקבל

$\displaystyle f(n)\geq \sum _{i=1}^{n/4}\sum _{j=3n/4}^{n}[\Omega (n)]=\Theta (n^{3})$.

שיטה ב'

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

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

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

נבצע החלפת משתנים $\displaystyle i'=n-i$, ונקבל:

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