מבני נתונים ואלגוריתמים - מחברת קורס/שיעורי בית 5/תשובות

1

הוכחה א'

נגדיר את אורך המסלול הארוך ביותר כ$\displaystyle h$, ונשאל את השאלה הבאה: בעץ שגובהו (אורך המסלול הארוך ביותר משורש לעלה) $\displaystyle h$, כמה צמתים אפשר לשים לכל היותר?

נשים לב שאם יש צומת שאין לו שני ילדים, אפשר לבנות עץ גדול יותר על ידי הוספת ילד אליו. מכאן נקבל שהעץ המכיל את מספר הצמתים המקסימאלי מבין הצמתים שגובהם $\displaystyle h$, הוא עץ שבו כל מסלול משורש לעלה הוא בגובה $\displaystyle h$, ולכל צומת (למעט העלים) יש שני ילדים.

בעץ כזה, ברמה הראשונה יש 1 צומת, ברמה הבאה 2 צמתים, וברמה ה$\displaystyle i$ יש $\displaystyle 2^{i-1}$ צמתים. נקבל שמספר הצמתים הוא $\displaystyle \sum _{i=1}^{h}2^{i-1}=2^{h}-1$. זה המספר המקסימאלי של הצמתים. לכן, עבור כל עץ שגובהו h ומספר צמתיו $\displaystyle n$, בהכרח מתקיים $\displaystyle n\leq 2^{h}-1\leq 2^{h}$. מלקיחת $\displaystyle \log$ משני האגפים נקבל $\displaystyle h=\Omega (\log(n))$.

הוכחה ב' (מבוססת על מגבלות דחיסה)

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

נגדיר את אורך המסלול הארוך ביותר כ$\displaystyle h$

נניח ש$\displaystyle a_{1},\ldots a_{n}$ היא קבוצת שמות שידועה לשולח ולמקבל. השולח רוצה להודיע על שם אחד מתוך הקבוצה הידועה. לדוגמה, קבוצת השמות יכולה להיות רשימת המתמודדים על נשיאות ארה"ב, וכתב עיתון מעוניין לשלוח למערכת את שם הזוכה.

משפט: בכל שיטת קידוד, יש הודעה אחת לפחות שארכה $\displaystyle \Omega (\log(n))$.

(הטענה נובעת משיקולים קומבינטוריים דומים מאד לאלה של החסם התחתון על מיון מבוסס-השוואות שראינו.)

מצד שני, כל עץ חיפוש בינרי יכול לשמש לקידוד צומת. השולח מחפש את הצומת בעץ, מהצומת למטה (כפי שראינו בחיפוש בעץ בינרי). בכל צומת, אם הוא פונה שמאלה הוא מסמן 0, ואם פונה ימינה, הוא מסמן 1. השולח משדר את רצף הביטים למקבל. ברור שהמקבל יכול מתוך רצף הביטים (והעץ) למצא את הצומת המתאים.

נשים לב שמספר הביטים שנשלח הוא בדיוק מספר הקשתות מצומת השורש לצומת הנבחר. לכן, יש לפחות מסלול אחד שארכו $\displaystyle \Omega (\log(n))$.

2

א'

זמן הריצה של Member

להלן פסוודו-קוד אפשרי לMember:

# Searches a tree (t) for a key (k).
# Returns whether the tree contains the key.
Find(t, k)
1	nd = t.root

ְ2	while nd != Nil
3		if k < nd.key
4			nd = nd.l-child
5		else if k > nd.key
6			nd = nd.r-child
7		else
8			return True
		
9	return False

אם מספר הצמתים בתת עץ בגובה $\displaystyle h$ הוא $\displaystyle \Theta (2^{h})$, אז קיים קבוע $\displaystyle c>0$, כך שמספר הצמתים בתת-העץ הוא לכל היותר $\displaystyle c\cdot 2^{h}$. נשים לב שבכל איטרציה, אם הצומת לא נמצא (7-8), אז באיטרציה הבאה נמצאים בצומת שגובהו נמוך ב1(בגלל 3-4 או 5-6). לכן:

1. באיטרציה הראשונה, מספר הצמתים בתת-העץ הוא לכל היותר $\displaystyle c\cdot 2^{h}$.
2. באיטרציה השניה, מספר הצמתים בתת-העץ הוא לכל היותר $\displaystyle c\cdot 2^{h-1}={\frac {c}{2}}\cdot 2^{h}$.
3. באיטרציה השלישית, מספר הצמתים בתת-העץ הוא לכל היותר $\displaystyle c\cdot 2^{h-2}={\frac {c}{4}}\cdot 2^{h}$.
4. ...

נקח $\displaystyle i=\left\lceil h+\log(c)\right\rceil$. אז $\displaystyle c\cdot 2^{h-i}=2^{h+\log(c)-\left\lceil h+\log(c)\right\rceil }\leq 1$, ולכן ב$\displaystyle \Theta (h)$ איטרציות נגיע לתת-עץ בגודל 1 (צומת יחיד).

בפרט, אם ניקח עץ בעל $\displaystyle n$ איברים, אז $\displaystyle n=\Theta (2^{h})$, ולכן $\displaystyle h=\Theta (\log(n))$.

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

אופטימאליות

כבר ראינו שMember צריך $\displaystyle O(\log(n))$ איטרציות בעץ דחוס, ולכן זהו חסם מלעיל על זמן ריצת חיפוש בעץ דחוס. מצד שני, בחסם תחתון על אורך המסלול הארוך ביותר ראינו בכל עץ חיפוש בינרי בעל $\displaystyle n$ איברים, יש מסלול אחד לפחות בעל $\displaystyle \Omega (\log(n))$ איברים, וזהו חסם תחתון כללי על חיפוש בעץ במקרה הגרוע. החסמים, לכן, מתלכדים כאן.

ב'

מיקום הצומת הk-קטן ביותר

משפט: הצומת ה$\displaystyle h$ בגובה במסלול השמאלי ביותר בעץ, הוא ראשו של תת-עץ המכיל את $\displaystyle \Theta (2^{h})$ האיברים הקטנים ביותר בעץ.

תת עץ של הצומת בגובה h במסלול השמאלי.

הוכחה: היות שהעץ הוא דחוס, אז צומת בגובה $\displaystyle h$ (בפרט אחד במסלול השמאלי ביותר בעץ), מכיל $\displaystyle \Theta (2^{h})$ איברים.

כעת נוכיח שהאיברים בתת-עץ הם האיברים הקטנים ביותר בעץ.

אם הצומת הוא ראש העץ, אז ברור שאין איברים גדולים מהם (כי אין איברים אחרים מהם).

אם הצומת אינו ראש העץ, אז יש לו אב, $\displaystyle a$.

מיקום צמתים בעלי מפתחות קטנים מצומת נתון - לא צאצא ימני.

נשים לב ש$\displaystyle a$ אינו צאצא ימני של אף צומת (מדוע?), ולכן כל האיברים הקטנים ממנו נמצאים בתת עץ השמאלי שלו.

מהמשפט הקודם נובע שהאיבר ה$\displaystyle k$ הקטן ביותר נמצא בתת עץ שראשו הוא צומת בגובה $\displaystyle \Theta (\log(k))$ במסלול השמאלי ביותר.

שינויים בעץ

נוסיף לעץ עוד (מצביע ל)צומת הקטן ביותר, min:

Binary-Search-Tree
	# The root (shoresh).
1	root	
	# Number of nodes.
2	size
	# The smallest node.
3	min

נדאג לעדכן איבר זה בפעולות Insert וDelete (הדבר אינו מסובך במיוחד, ולא נציג את הפסוודו-קוד כאן).

שינויים בMember

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

Member(t, x)
	# Loop upward starting from the leftmost node.

1	nd = t.min

2	while nd.parent != Nil and nd.parent.key < x
3		nd = nd.parent

	# Now loop down again.

4	while nd != Nil
5		if k < nd.key
6			nd = nd.l-child
7		else if k > nd.key
8			nd = nd.r-child
9		else
10			return True

11	return False

3

משפט כללי

כדי לפתור את התשובה, נוכיח ראשית את המשפט הפשוט הבא:

משפט: בעץ חיפוש בינרי בעל מפתחות שונים זה מזה, נניח שצומת $\displaystyle a$ מחזיק מפתח כלשהו. אז: הצאצאים השמאליים של $\displaystyle a$ מכילים כולם מפתחות קטנים ל$\displaystyle a$. יש עוד צמתים עם מפתחות קטנים מ$\displaystyle a$ מעבר לכך אם ורק אם $\displaystyle a$ הוא צאצא ימני (לאו דווקא ישיר) של צומת כלשהו.

להלן דוגמה למה שהמשפט אומר.

דוגמה: בתרשים הבא, $\displaystyle a$ אינו צאצא ימני של אף צומת. צמתי המפתחות הקטנים ממנו (הצבועים באפור), כולם בתת העץ הימני שלו. מיקום צמתים בעלי מפתחות קטנים מצומת נתון - לא צאצא ימני. לעומת זאת, בתרשים הבא, $\displaystyle a$ הוא צאצא ימני (לא ישיר) של $\displaystyle b$. צמתי המפתחות הקטנים ממנו (הצבועים באפור), בתת העץ הימני שלו וגם בתת העץ השמאלי של $\displaystyle b$. מיקום צמתים בעלי מפתחות קטנים מצומת נתון - צאצא ימני.

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

הקשר ללא מידע נוסף

מהמשפט הכללי ברור שאי אפשר לקבוע האם הצומת של $\displaystyle y$ הוא צאצא של הצומת של $\displaystyle x$. ייתכן שהצומת של $\displaystyle y$ הוא צאצא שמאלי של הצומת של $\displaystyle x$, אך אם הצומת של $\displaystyle x$ הוא צאצא ימני של צומת כלשהו, ייתכן שהצומת של $\displaystyle y$ הוא צאצא שמאלי של אותו הצומת.

הקשר עם מידע נוסף

ראשית, ברור שכל אחד בנפרד מסדרו של צומת במעבר in-order,‏ post-order,‏ או מספר צאצאיו, אינו מספיק כדי לקבוע יחס צאצא-אב.

נתבונן שוב במקרה בו צומת $\displaystyle a$ הוא צאצא ימני של צומת $\displaystyle b$.

מיקום צמתים בעלי מפתחות קטנים מצומת נתון - צאצא ימני.

1. אם $\displaystyle y<x$, אז $\displaystyle y$ יודפס לפני $\displaystyle x$ במעבר in-order בכל מקרה. אבל אם $\displaystyle x=a$, אז $\displaystyle y$ יכול להיות צאצא שמאלי של $\displaystyle x$, או צאצא שמאלי של הורה של $\displaystyle x$ (לדוגמה $\displaystyle b$).
2. באופן דומה, אם $\displaystyle y<x$, אז $\displaystyle y$ יודפס לפני $\displaystyle x$ במעבר post-order בכל מקרה. אבל שוב, אם $\displaystyle x=a$, אז $\displaystyle y$ יכול להיות צאצא שמאלי של $\displaystyle x$, או צאצא שמאלי של הורה של $\displaystyle x$ (לדוגמה $\displaystyle b$).
3. כפי שהתרשים מראה, אם $\displaystyle x<y$, אין בהכרח שום קשר בין מספר האיברים בתת-העץ של $\displaystyle x$ לבין זה של $\displaystyle y$.

לעומת זאת, השילוב של סדר post-order וdescendants מספיק.

משפט: נגדיר: $\displaystyle p_{l}$ הוא מספר הpost-order של ילדו השמאלי של $\displaystyle x$. $\displaystyle d_{l}$ הוא מספר הdescendants של ילדו השמאלי של $\displaystyle x$. אז כל צומת בתת העץ השמאלי הוא בעל מספר post-order ב$\displaystyle \left\{p_{l}-d_{l}+1,\ldots ,p_{l}\right\}$.

הוכחה: מספרי הpost-order של ילדו השמאלי של $\displaystyle x$ הם $\displaystyle d_{l}$ מספרים עוקבים, שהאחרון שבהם הוא $\displaystyle p_{l}$.

מהמשפט האחרון ברור כיצד יש למצוא האם צומת כלשהו nd-y הוא צאצא של צומת כלשהו nd-x, בהנחה שתוכן הראשון הוא $\displaystyle y$, תוכן השני הוא $\displaystyle x$, ו$\displaystyle y<x$:

1. אם לnd-x אין ילד שמאלי - התשובה שלילית.
2. אחרת:
   1. קובעים כ$\displaystyle p_{l}$ את Postorder-Num(nd.l-child).
   2. קובעים כ$\displaystyle d_{l}$ את Descendants(nd.l-child).
   3. בודקים האם {Postorder-Num(nd-y) גדול או שווה ל$\displaystyle p_{l}-d_{l}+1$.

עכשיו תורכם: חשוב האם שילובי פונקציות שונים יפתרו את הבעיה גם כן.

4

המבנה הרקורסיבי

נגדיר כ$\displaystyle m(i)$ את המכפלה הגדולה ביותר האפשרית של תת-סידרה בדלנית של $\displaystyle [x_{1},...,x_{i}]$ (שים לב שתת-הסדרה אינה בהרכח משתמשת ב$\displaystyle x_{i}$).

משפט: $\displaystyle m(i)$ מקיימת את נוסחת הנסיגה הבאה: אם $\displaystyle i=1$, אז $\displaystyle m(i)=x_{1}$. אם $\displaystyle i=2$, אז $\displaystyle m(i)=\max\{x_{1},x_{2}\}$. אם $\displaystyle i>2$, אז $\displaystyle m(i)=\max\{m(i-1),m(i-2)\cdot x_{i}\}$.

הוכחה: נשים לב לנקודות הבאות:

1. אם $\displaystyle i=1$, אז בוודאי שנבחר באיבר הראשון (כל איבר הוא לפחות 1); נקבל בהכרח $\displaystyle x_{1}$.
2. אם $\displaystyle i=2$, אז בוודאי שנבחר באיבר הראשון או באיבר השני (כל איבר הוא לפחות 1); נקבל בהכרח $\displaystyle \max\{x_{1},x_{2}\}$.
3. אם $\displaystyle i>2$, אז או שנבחר ב$\displaystyle x_{i}$ או שלא (אלו שתי האפשרויות היחידות).
   • אם נבחר ב$\displaystyle x_{i}$, אז לא נוכל לבחור ב$\displaystyle x_{i-1}$; במקרה זה נרצה להכפיל את $\displaystyle x_{i}$ בתוצאה הטובה ביותר האפשרית עד $\displaystyle i-2$, שהיא $\displaystyle m(i-2)$.
   • אם לא נבחר את $\displaystyle x_{i}$, אז נרצה את תת-הסדרה הטובה ביותר עד $\displaystyle i-1$, שהיא, עפ"י ההגדרה, $\displaystyle m(i-1)$.

בנקודה השלישית, היות שאיננו יודעים אם כדאי לבחור את האיבר ב$\displaystyle i$ או לא - ניקח את המקסימום משתי האפשרויות.

מימוש רקורסיבי נאיבי

להלן פסוודו-קוד המממש רעיון זה:

Max-Product(i)
1	if i == 1
2		return X[1]

3	if i == 2
4		return max(X[1], X[2])

6	guess-with = Max-Product(i - 2) * X[i]
7	guess-without = Max-Product(i - 1)
		
8	if guess-with > guess-without
9		return guess-with
10	else
11		return guess-without

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

שימוש בmemoization

להלן פסוודו-קוד יעיל יותר:

1	L = Make-Array(n)

2	for i in [1, ..., n]
3		L[i] = Nil


Max-Product(i)
1	if L[i] != Nil
2		return L[i]

3	if i == 1
4		L[1] = X[1]
5		return L[1]

6	if i == 2
7		L[2] = max(X[1], X[2])
8		return L[2]

9	guess-with = Max-Product(i - 2) * X[i]
10	guess-without = Max-Product(i - 1)
		
11	if guess-with > guess-without
12		L[i] = guess-with
12		return L[i]
13	else
14		L[i] = guess-without
15		return L[i]

הדפסת האיברים

להלן פסוודו-קוד המאפשר גם הדפסת תת-הסדרה:

1	L = Make-Array(n)
2	U = Make-Array(n)

3	for i in [1, ..., n]
4		L[i] = Nil


Max-Product(i)
1	if L[i] != Nil
2		return L[i]

3	if i == 1
4		L[1] = X[1]
5		U[1] = True
6		return L[1]

7	if i == 2
8		L[2] = max(X[1], X[2])
9		U[2] = X[2] == L[2]? True : False
10		return L[2]

11	guess-with = Max-Product(i - 2) * X[i]
12	guess-without = Max-Product(i - 1)
		
13	if guess-with > guess-without
14		L[i] = guess-with
15		U[i] = True
16		return L[i]
17	else
18		L[i] = guess-without
19		U[i] = False
20		return L[i]

המערך U מחזיק בכניסה ה$\displaystyle i$ את ההכרעה האם תת-הסדרה הטובה ביותר עד $\displaystyle i$ אכן משתמשת באיבר ה$\displaystyle i$ או לא. קטע הקוד הבא מראה כיצד להדפיס את האינדקסים של תת-הסידרה הטובה ביותר המסתיימת ב$\displaystyle i$.

Print-Seq(i)
1	if U[i] == True
2		Print-Seq(i - 2)
3		Print(i)
4		return
	
5	Print-Seq(i - 1)

כיצד נשתמש בקוד, אם כן?

1. נאתחל המשתנים הגלובליים, ונקרא לMax-Product(n).
2. נקרא לPrint-Seq(n).

ניתוח סיבוכיות

הסיבוכיות הכוללת הנה לינארית:

• מהתבוננות, ברור שהאתחול לינארי.
• הסיבוכיות של Max-Product(n) נתון על ידי $\displaystyle \sum _{i=1}^{n}[T'(i)]$, כאשר $\displaystyle T'(i)=O(1)$ הוא זמן הריצה של Max-Product(i) בהנחה שכל קריאה רקורסיבית היא $\displaystyle O(1)$ (ראו הניתוח בדג הסלמון).
• מהתבוננות, קל לראות שהדפסת האיברים היא $\displaystyle O(n)$.

5

ראשית נניח שהמערך Mממויין, או, לחלופין, נמיין אותו בעזרת מיון מיזוג בסיבוכיות $\displaystyle \Theta (n\cdot \log(n))$.

נגדיר כ$\displaystyle mp(i)$ את מירב הרווח שאפשר להרוויח מפתיחת סניפים הלקוחים מתוך $\displaystyle i$הבתים הראשונים.

משפט: לפי הגדרת $\displaystyle mp(i)$: הפתרון הטוב ביותר הוא בעל רווח $\displaystyle mp(n)$. הפונקציה נתונה על ידי נוסחת הנסיגה: $\displaystyle mp(1)=p_{1}$ לכל $\displaystyle i>1$,‏ $\displaystyle mp(i)=\max \left\{p_{i}+\max _{j|m_{i}-m_{j}>k}mp(j),mp(i-1)\right\}$ $\displaystyle mp(i)$ מונוטונית לא-יורדת ב$\displaystyle i$.

הוכחה: (2) אם $\displaystyle i=1$, אז ברור שהפתרון הרווחי ביותר הוא זה שבו בוחרים את הבית הראשון (והיחידי האפשרי לבחירה). אם $\displaystyle i>1$, אז או שבוחרים את בית $\displaystyle i$, או שלא. במקרה הראשון, מרוויחים $\displaystyle p_{i}$ מהבחירה בבית, אך לפניו אסור לבחור באף בית בעל מיקום שהפרשו מ$\displaystyle m_{i}$קטן מ$\displaystyle k$. במקרה השני, הרווח הוא בדיוק הרווח כשמותר לבחור מבין $\displaystyle i-1$הבתים הראשונים.

להלן פסוודו-קוד המממש נוסחה זו.

Max-Profit(M, P, k, i)
1	if i == 0
2		return 0
		
3	if i == 1
4		return P[1]
		
5	guess-without = Max-Profit(i - 1)
6	guess-with = P[i]
		
7	if m[i] > k
8		j = Find-Index(M, M[i] - k)
9		guess-with = guess-with + Max-Profit(M, P, k, j)
			
10	if guess-with > guess-without
11		return guess-with
12	else
13		return guess-without

חשוב רק לשים לב לקריאה לפונקציה Find-Index ב8. פונקציה זו מוצאת את האינדקס הגדול ביותר בMשקטן מM[i] - k. היות שMממויין, נוכל לעשות זאת על ידי שינוי קטן בחיפוש בינרי. נוסיף גם Memoization:

1	MP = Make-Array(n)
	
2	for i in [1, ..., n]
3		MP[i] = Nil


Max-Profit(M, P, k, i)
1	if i == 0
2		return 0
		
3	if MP[i] != Nil
4		return MP[i]
		
5	if i == 1
6		MP[1] = P[1]
7		return P[1]
		
8		guess-without = Max-Profit(i - 1)
9		guess-with = P[i]
		
10	if m[i] > k
11		j = Find-Index(M, M[i] - k)
12		guess-with = guess-with + Max-Profit(M, P, k, j)
			
13	if guess-with > guess-without
14		MP[i] = guess-with
15		return guess-with
16	else
17		MP[i] = guess-without
18		return guess-without

כעת נוסיף גם את הדפסת האיברים:

1	MP = Make-Array(n)
2	Used = Make-Array(n)
	
3	for i in [1, ..., n]
4		MP[i] = Nil


Max-Profit(M, P, k, i)
1	if i == 0
2		return 0
		
3	if MP[i] != Nil		
4		return MP[i]
		
5	if i == 1
6		MP[1] = P[1]
7		Used[1] = True
8		return P[1]
		
9		guess-without = Max-Profit(i - 1)
10		guess-with = P[i]
		
11	if m[i] > k
12		j = Find-Index(M, M[i] - k)
13		guess-with = guess-with + Max-Profit(M, P, k, j)
			
14	if guess-with > guess-without
15		MP[i] = guess-with
16		Used[i] = True
17		return guess-with
18	else
19		MP[i] = guess-without
20		Used[i] = False
21		return guess-without

המערך Used מתאר האם השתמשנו באיבר ה$\displaystyle i$או לא. נשתמש בו ע"י קריאה לPrint-Nums(k, n), כאשר Print-Nums מוגדרת כך:

Print-Nums(k, i)
1	if i &lt 1
2		return
		
3	if Used[i]
4		j = Find-Index(M, M[i] - k)
5		Print-Nums(k, j)
6	else
7		Print-Nums(k, i - 1)
			
8	if Used[i]
9		Print(i)

נותר רק לנתח את הסיבוכיות.

השורה j ← Find-Index(M, M[i] - k)אורכת $\displaystyle O(\log(n))$. אם נגדיר כ$\displaystyle T'(i)$ את זמן הקריאה לMax-Profit(M, P, k, i)בהנחה שכל קריאה רקורסיבית היא $\displaystyle O(1)$, אז $\displaystyle T'(i)=O(\log(n))$, והסיבוכיות היא $\displaystyle O(n\cdot \log(n))$. מצד שני, מיון המערך הוא $\displaystyle \Omega (n\cdot \log(n))$, ולכן נקבל $\displaystyle \Theta (n\cdot \log(n))$.

6

הפתרון דומה מאד להוכחת הטענה שעצים אדומים-שחורים הם לוגריתמיים. נניח שגובה העץ הוא $\displaystyle h$. מה מספר המפתחות הקטן ביותר היכול להיות בעץ? קל לראות שזה המספר המתקבל כאשר כל אחד מהצמתים הוא מסוג Bar. במצב זה, היות שעל פי הנתונים כל המסלולים משורש לעלה הם בעלי אותו אורך, נקבל שמספר המפתחות הוא לכל הפחות $\displaystyle \sum _{i=1}^{h}\left[2^{i-1}\right]=2^{h}-1$. הפתרון, לכן, מתקבל על ידי פתירת אי-השוויון $\displaystyle n\geq 2^{h}-1$:

$\displaystyle n\geq 2^{h}-1\Rightarrow$
$\displaystyle n\geq 2^{h}/2\Rightarrow$
$\displaystyle \log(n)\geq h-1\Rightarrow$
$\displaystyle h=O\left(\log(n)\right)$