שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2010 - סיבוכיות

מה ניתן להגיד על $\sum_{i=1}^{n} i \log i$? הסכום הזה הוא: א( $\Theta(n^2 \log n)$ ב( $\Theta(n^2)$ ג( $\Theta(n \log^2 n)$ ד( $\Theta(n \log n \log \log n)$ ה( אף אחת מהתשובות א) עד ד) אינה נכונה.

רמז: ניתן לחסום את הסכום מלמעלה ומלמטה. עבור החסם התחתון, הסתכלו רק על המחצית השנייה של האיברים בסכום, מהאיבר $\lceil n/2 \rceil$ ועד $n$.

פתרון: כדי למצוא את החסם האסימפטוטי של הסכום $\sum_{i=1}^{n} i \log i$, נשתמש בשיטת החסימה (bounding). נמצא חסם עליון (Big-O) וחסם תחתון (Big-Omega) לסכום, ואם הם מאותו סדר גודל, נסיק שזהו גם החסם ההדוק (Theta). **חסם עליון (O):** כל איבר בסכום, $i \log i$, קטן או שווה לאיבר האחרון והגדול ביותר, $n \log n$. לכן, ניתן לחסום את הסכום על ידי: $$ \sum_{i=1}^{n} i \log i \le \sum_{i=1}^{n} n \log n = n \cdot (n \log n) = n^2 \log n $$ מכאן, הסכום הוא $O(n^2 \log n)$. **חסם תחתון ($\Omega$):** כדי למצוא חסם תחתון, נתבונן רק במחצית השנייה של איברי הסכום, כלומר מהאיבר $\lceil n/2 \rceil$ עד האיבר $n$. כל איבר בחלק זה של הסכום גדול או שווה ל-$\frac{n}{2} \log(\frac{n}{2})$. $$ \sum_{i=1}^{n} i \log i \ge \sum_{i=\lceil n/2 \rceil}^{n} i \log i $$ מספר האיברים בחלק זה הוא $n - \lceil n/2 \rceil + 1$, שהוא בקירוב $n/2$. נחסום כל איבר באיבר הקטן ביותר בחלק זה: $$ \sum_{i=\lceil n/2 \rceil}^{n} i \log i \ge \sum_{i=\lceil n/2 \rceil}^{n} \frac{n}{2} \log\left(\frac{n}{2}\right) $$ $$ = (n - \lceil n/2 \rceil + 1) \cdot \frac{n}{2} \log\left(\frac{n}{2}\right) $$ מכיוון ש-$n - \lceil n/2 \rceil + 1 \ge n/2$, נקבל: $$ \ge \frac{n}{2} \cdot \frac{n}{2} \log\left(\frac{n}{2}\right) = \frac{n^2}{4} (\log n - \log 2) $$ הביטוי $\frac{n^2}{4} (\log n - \log 2)$ הוא מסדר גודל של $n^2 \log n$. לכן, הסכום הוא $\Omega(n^2 \log n)$. **מסקנה:** הראינו שהסכום הוא גם $O(n^2 \log n)$ וגם $\Omega(n^2 \log n)$. לפי **הגדרת סימון $\Theta$**, אם $f(n) = O(g(n))$ וגם $f(n) = \Omega(g(n))$, אז $f(n) = \Theta(g(n))$. לכן, $\sum_{i=1}^{n} i \log i = \Theta(n^2 \log n)$. התשובה הנכונה היא א. $\blacksquare$