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

		הדף נמצא בשלבי עבודה: כדי למנוע התנגשויות עריכה ועבודה כפולה אתם מתבקשים שלא לערוך ערך זה בטרם תוסר הודעה זו, אלא אם כן תיאמתם זאת עם מניחי התבנית.
		אם הדף לא נערך במשך שבוע ניתן להסיר את התבנית ולערוך אותו, אך רצוי לתת קודם תזכורת בדף שיחת הכותבים.	שיחה

א'

להלן הוכחה שגויה לכך שכל אחת מהפעולות למעבר על כל איברי העץ שראינו Post-Order In-Order, וIn-Order), פועלת בזמן ריבועי במספר האיברים בעץ.

הוכחה: ההוכחה באינדוקציה על מספר הצמתים, $\displaystyle n$.

(בסיס האינדוקציה) עבור $\displaystyle n=1$, $\displaystyle T(1)=O(1)=O(1^{2})$.

(מעבר האינדוקציה) כבר ראינו שזמן הריצה נתון ע"י נוסחת הנסיגה $\displaystyle T(n)=T(i)+T(n-i)+O(i)$. נשמתש בהנחת האינדוקציה, ונקבל

T(n) = \Theta(i^2) + \Theta((n - i)^2)

ב'

מה בעייתי בהוכחה הבאה לכך שזמן הריצה הוא לינארי?