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

נוכיח באינדוקציה שקיים $\displaystyle c>0$ כך ש(עבור $\displaystyle n$-ים מספיק גדולים) $\displaystyle T(n)\leq c\cdot n\cdot \log(n)$.

(מעבר האינדוקציה) עפ"י נוסחת הנסיגה והנחת האינדוקציה,

$\displaystyle T(n)=\max _{i=1,\ldots ,n/2}[T(i)+T(n-i)+\Theta (i)]\leq$
$\displaystyle \max _{i=1,\ldots ,n/2}[c\cdot i\cdot \log(i)+c\cdot (n-i)\cdot \log(n-i)+c'\cdot i]$
עבור קבוע $\displaystyle c'>0$ כלשהו.

נגזור את הביטוי שבתוך ה$\displaystyle \max$, ונקבל $\displaystyle c\cdot \log(i)-c\cdot \log(n-i)+c'$

נגזור את הביטוי פעם שניה, ונקבל ביטוי חיובי. מכאן ברור שמקסימום הביטוי הוא כאשר$\displaystyle i=n/2$.

כאשר$\displaystyle i=n/2$, אז

$\displaystyle T(n)\leq 2\cdot c\cdot n/2\cdot \log(n/2)+c'=$
$\displaystyle c\cdot n\cdot \log(n)-c\cdot n+c'\leq$
$\displaystyle c\cdot n\cdot \log(n)$

(בסיס האינדוקציה) נפתור: $\displaystyle (c\cdot i\cdot \log(i))|^{i=2,3}=O(1)$
ונווכח שהדבר נכון עבור $\displaystyle c$ גדול מספיק.