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

מצד אחד, כל טור גדול לפחות כמו איברו הראשון. מכאן נקבל: $\displaystyle \sum _{j=1}^{h}[2^{-j}\Theta (j)]\geq [2^{-1}\Theta (1)]\geq \Theta (1)$ ולכן הטור המקורי הוא $\displaystyle \Omega (1)$.

מצד שני, נקבל $\displaystyle \sum _{j=1}^{h}[2^{-j}\Theta (j)]\leq \sum _{j=1}^{\infty }[2^{-j}\Theta (j)]=\Theta \left(\sum _{j=1}^{\infty }[2^{-j}j]\right)$, ולכן נחסום מלמעלה את $\displaystyle \sum _{j=1}^{\infty }[2^{-j}j]$.

עבור ערכי $\displaystyle j$ מספיק גדולים, $\displaystyle 2^{-j}j<1.5^{-j}$ (קל לראות זאת מל'וספיטל, לדוגמה). נגדיר את $\displaystyle k$ כאינדקס הראשון בו $\displaystyle 2^{-k}k<1.5^{-k}$. נקבל $\displaystyle \sum _{j=1}^{\infty }[2^{-j}j]=\sum _{j=1}^{k-1}[2^{-j}j]+\sum _{j=k}^{\infty }[2^{-j}j]\leq O(1)+\sum _{j=k}^{\infty }[1.5^{-j}]\leq O(1)+\sum _{j=1}^{\infty }[1.5^{-j}]=O(1)+O(1)=O(1)$

כדאי לדעת: אפשר לפתור את התרגיל גם בעזרת חסמי האינטגרלים לטורים שראינו.