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

הפונקציה $\displaystyle T(n)$ נתונה על ידי הנוסחה. $\displaystyle T(n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]$.

אנא הוכח $\displaystyle T(n)=\Theta (n^{3})$.

רמז נסה להוכיח זאת באותו אופן בו הוכחנו $\displaystyle \sum _{i=1}^{n}[\log(i)]=\Theta (n\cdot \log(n))$. כלומר: הוכח בנפרד חסמי $\displaystyle O$ ו$\displaystyle \Omega$. ערוך מניפולציות על איבר הטור הכללי ועל גבולות הסיכום כך שיתקבל איבר טור שאינו תלוי בגבולות הסיכום (ולכן ניתן יהיה להוציאו מחוץ לסכום).