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

מבני נתונים ואלגוריתמים - מחברת קורס

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

1

שיטה א'

נשתמש באותו הרעיון בו השתמשתנו כדי לנתח טור של לוגריתמים.

ראשית נראה כי $\displaystyle f(n)=O(n^{3})$ .

הוכחה: $\displaystyle f(n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]\leq \sum _{i=1}^{n}\sum _{j=1}^{n}[\Theta (n)]=\Theta (n^{3})$
.

כעת נראה כי $\displaystyle f(n)=\Omega (n^{3})$ .

הוכחה: $\displaystyle f(n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]\geq \sum _{i=1}^{n/4}\sum _{j=i}^{n}[\Theta (j-i+1)]\geq \sum _{i=1}^{n/4}\sum _{j=3n/4}^{n}[\Theta (j-i+1)]$ .
נשים לב שכאשר $\displaystyle i$ בתחום $\displaystyle 1,\ldots ,n/4$ ו $\displaystyle j$ בתחום $\displaystyle 3n/4,\ldots ,n$ , אז $\displaystyle \Theta (j-i+1)=\Omega (n/2)=\Omega (n)$ .

לכן נקבל

$\displaystyle f(n)\geq \sum _{i=1}^{n/4}\sum _{j=3n/4}^{n}[\Omega (n)]=\Theta (n^{3})$ .

שיטה ב'

$\displaystyle f(n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]$ .

נשים לב שעבור ערך $\displaystyle i$ כלשהו, נוכל לבצע את החלפת המשתנים $\displaystyle j'=j-i$ , ונקבל $\displaystyle \sum _{j=i}^{n}[\Theta (j-i+1)]=\sum _{j'=0}^{n-i}[\Theta (j'+1)]=\sum _{j'=0}^{n-i}[\Theta (j')]=\Theta ((n-i)^{2})$ .

נציב זאת חזרה בסכום הכפול: $\displaystyle f(n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]=\sum _{i=1}^{n}[(n-i)^{2}]$ .

נבצע החלפת משתנים $\displaystyle i'=n-i$ , ונקבל:

$\displaystyle f(n)=\sum _{i=1}^{n}[(n-i)^{2}]=\sum _{i'=0}^{n-1}[i'^{2}]=\Theta (n^{3})$ .

2

א'

1

$\displaystyle T(n)=\Theta (n^{\log _{2}(3)})$ , עפ"י מקרה 1 של משפט המאסטר.

2

נפרוש את הנוסחה: $\displaystyle T(n)=$
$\displaystyle T(n-1)+\log(n)=$
$\displaystyle T(n-2)+\log(n-1)+\log(n)=$
$\displaystyle T(n-3)+\log(n-2)+\log(n-1)+\log(n)=$
$\displaystyle \cdots$
$\displaystyle \sum _{i=1}^{n}[\log(i)]=$
$\displaystyle \Theta (n\cdot \log(n)).$
(את המעבר האחרון ראינו בטורים שימושיים.)

3

נגדיר $\displaystyle \alpha '=1-\alpha$ . בלי הגבלת הכלליות, נניח ש $\displaystyle \alpha <\alpha '$ . להלן עץ הפרישה המתקבל:

בעץ זה, לכל אחד מהצמתים המצויירים שני ילדים: אם הצומת מתאים לגודל $\displaystyle n'$ , אז הילד השמאלי מתאים ל $\displaystyle \alpha n'$ ,‏ והימני מתאים ל $\displaystyle \alpha 'n'$ ,‏. מכאן אפשר לראות שמסלולים שמאליים בעץ קצרים יותר ממסלולים ימניים, כי $\displaystyle \alpha '=1-\alpha$ .‏ לא כל הרמות בעץ מלאות, אם כן, מה שמקשה מעט על ניתוח הסיבוכיות. נגדיר כ $\displaystyle h_{min}$ את אורך המסלול השמאלי ביותר, וכ $\displaystyle h_{\max }$ את אורך המסלול הימני ביותר.

קל לראות שכל רמה מלאה בעץ תורמת $\displaystyle \Theta (n)$ .‏ הרמה הראשונה תורמת $\displaystyle \Theta (n)$ ;‏ הרמה השניה תורמת $\displaystyle \Theta (\alpha n)+\Theta (\alpha 'n)=\Theta (n)$ ,‏ הרמה השלישית תורמת $\displaystyle \Theta (\alpha ^{2}n)+\Theta (\alpha \alpha 'n)+\Theta (\alpha '\alpha n)+\Theta (\alpha '^{2}n)=\Theta (\alpha n)+\Theta (\alpha 'n)\Theta (n)$ ;‏ וכו'.‏ (אפשר להראות זאת פורמאלית באינדוקציה.)

אפשר לראות, לכן, ש $\displaystyle T(n)$ חסומה מלמטה ע"י $\displaystyle h_{min}\cdot \Theta (n)$ , וחסומה מלמעלה ע"י $\displaystyle h_{\max }\cdot \Theta (n)$ . אבל היות ש $\displaystyle h_{min}=\Theta (\log(n))$ וכן $\displaystyle h_{\max }=\Theta (\log(n))$ , אז $\displaystyle T(n)=\Theta (n\cdot \log(n))$ .

ב'

נשתמש בפרישה.בעץ המתאים לנוסחה:

צומת הראש מציין את $\displaystyle T(n)$ , והרמה הראשונה תורמת $\displaystyle \log(n)$ .
ברמה הבאה, הצומת מציין את $\displaystyle T({\sqrt {n}})=t(n^{1/2})$ , והרמה תורמת $\displaystyle \log({\sqrt {n}})=1/2\cdot \log(n)$ .
ברמה הבאה אחריה, הצומת מציין את $\displaystyle T({\sqrt {n^{1/2}}})=t(n^{1/4})$ , והרמה תורמת $\displaystyle \log({\sqrt {n^{1/2}}})=1/4\cdot \log(n)$ .

החוקיות איננה מסובכת, ונוכל להוכיח את הטענה הבאה באינדוקציה פשוטה: ברמה ה $\displaystyle i$ (כאשר ראש העץ נחשב ברמה ה0), הצומת מציין את $\displaystyle T(n^{1/2^{i}})$ , והרמה תורמת $\displaystyle 1/2^{i}\cdot \log(n)$ .

כדי למצוא את גובה העץ, $\displaystyle m$ , נפתור $\displaystyle n^{1/2^{i}}=2$ : $\displaystyle n^{1/2^{m}}=2$
$\displaystyle \log(n^{1/2^{m}})=1$
$\displaystyle 1/2^{m}\cdot \log(n)=1$
$\displaystyle 2^{m}=\log(n)$
$\displaystyle m=\log(\log(n))$
כאמור, הרמה ה $\displaystyle i$ תורמת $\displaystyle 1/2^{i}\cdot \log(n)$ . נותר, לכן, לסכם את $\displaystyle \sum _{i=1}^{\log(\log(n))}[1/2^{i}\cdot \log(n)]$ : $\displaystyle \sum _{i=0}^{\log(\log(n))}[1/2^{i}\cdot \log(n)]=$
$\displaystyle \sum _{i=0}^{\log(\log(n))}[1/2^{i}]\cdot \log(n)=$
$\displaystyle \Theta (1)\cdot \log(n)=$
$\displaystyle \Theta (\log(n))$

3

הוכחה: נוכיח באינדוקציה שקיים $\displaystyle c>0$ כך ש $\displaystyle T(n)\geq c\cdot 1.5^{n}$ .

(מעבר האינדוקציה) נניח שהטענה נכונה עד (כולל) $\displaystyle n-1$ , ונוכיח שהיא נכונה ל $\displaystyle n$ .‏ עפ"י נוסחת הנסיגה, $\displaystyle T(n)=\sum _{i=1}^{n-1}[T(i)]+\Theta (n)\geq \sum _{i=1}^{n-1}[T(i)]+c'\cdot n$
עבור $\displaystyle c'$ כלשהו. לכן, עפ"י הנחת האינדוקציה, $\displaystyle T(n)\geq \sum _{i=1}^{n-1}[c\cdot 1.5^{i}]+c'\cdot n$ .
עפ"י הנוסחה לטור הנדסי,

$\displaystyle \sum _{i=1}^{n-1}[c\cdot 1.5^{i}]+c'\cdot n=$
$\displaystyle c\cdot 1.5^{1}(1.5^{n-1}-1)/(1.5-1)+c'\cdot n=$
$\displaystyle 2\cdot c\cdot 1.5^{1}(1.5^{n-1}-1)+c'\cdot n=$
$\displaystyle 2\cdot c\cdot 1.5^{n}-3\cdot c+c'\cdot n.$
אם ניקח $\displaystyle c<c'/3$ ,‏ אז הביטוי האחרון גדול מ $\displaystyle c\cdot 1.5^{n}$ .

(בסיס האינדוקציה) היות ש $\displaystyle T(1)=O(1)$ ,‏ אז $\displaystyle T(1)=c_{0}$ ,‏ עבור $\displaystyle c_{0}>0$ כלשהו. נפתור $\displaystyle T(1)=c_{0}\geq c\cdot 1.5^{1}$ ,‏ ונקבל $\displaystyle c\leq c_{0}/1.5$ .‏

האינדוקציה, לכן, נכונה עבור $\displaystyle 0<c<\min\{c_{0}/1.5,c'/3\}$ , החל מ $\displaystyle n=1$ .

4

פעולת הפונקציה

כדי להבין מה עושה הפונקציה כאשר היא מקבלת את הקלט $\displaystyle n$ , נחשוב על הייצוג הבינרי של $\displaystyle n$ , נניח $\displaystyle b_{h}b_{h-1}b_{2}b_{1}$ (כלומר נניח ש $\displaystyle n$ הנו מספר בעל $\displaystyle h$ ביטים, בעל הביט החשוב ביותר $\displaystyle b_{h}$ , והביט החשוב פחות $\displaystyle b_{1}$ ).

כעת נראה מה הפונקציה עושה.

בשורה 3, הביטוי $\displaystyle n\%2$ הוא בדיוק ערך הביט $\displaystyle b_{1}$ .
שוב בשורה 3, Foo( ⌊n / 2⌋ ) היא הקריאה לאותה פונקציה, אך עם הערך $\displaystyle b_{h}b_{h-1}b_{2}$ .

מכאן ברור שהפונקציה פשוט סוכמת את הביטים של $\displaystyle n$ . אפשר להראות זאת פורמלית באינדוקציה.

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

מהתבוננות בשלוש שורות הפונקציה, ברור שלמעט הקריאה הרקורסיבית, כל הפעולות הן בזמן קבוע. מכאן נקבל את נוסחת הנסיגה $\displaystyle T(n)=T(\left\lfloor n/2\right\rfloor )+O(1)$ . נזכר שוב שמותר לנו (בקורס זה) להתעלם משגיאות עיגול בנוסאות נסיגה של זמן ריצה, ולכן נוסחת הנסיגה היא $\displaystyle T(n)=T(n/2)+O(1)$ . כבר ראינו (בדף על נוסחאות נסיגה) שפתרון נוסחה זו הוא $\displaystyle \Theta (\log(n))$ .

5

1

במערך[2, 3, 8, 6, 1] ישנם חמשת ההיפוכים הבאים:

$\displaystyle (1,5)$
$\displaystyle (2,5)$
$\displaystyle (3,4)$
$\displaystyle (3,5)$
$\displaystyle (4,5)$

2

כדאי לדעת:

הפתרון משתמש ברעיון "divide and conquer", כלומר פתרון בעיות "גדולות" ע"י פתירת בעיות "קטנות" יותר.

הפתרון מתבסס על שינויים קלים במיון מיזוג. ראשית, נתבונן בפסוודו-קוד הבא, שהוא ווריאציה קלה על Merge:

	# A global variable that counts the number of inversions.
1	inv


# Merge and count inversions. 
# Takes two sorted arrays (L, R).
# Returns a sorted array of L ∪ R, and counts how many members
#	of L and R are inverted relative to each other.
Merge-Count-Inversions(L, R)
1	Merged = Make-Array( Length(L) + Length(R) )

2	l = r = m = 1

3	while l <= Length(L) or r <= Length(R)
4		if r > Length(R)
5			Merged[m++] = L[l++]
6			inv = inv + r - 1
7		else if l > Length(L)
8			Merged[m++] = R[r++]
9		else if L[l] inv = inv + r - 1
10			Merged[m++] = L[l++]
11			inv = inv + r - 1
12		else
13			Merged[m++] = R[r++]

14	return Merged

המשתנה הגלובלי inv (ב1) שומר על מספר ההפכים. הפונקציה Merge-Count-Inversions כמעט זהה לפונקציה Merge שאותה כבר פגשנו, למעט השורות 6 ו11 שנוספו - שורות אלה מעדכנות את inv בכל פעם שנלקח איבר מL.

משפט:

אם Merge-Count-Inversions נקראת עם L וR ממוינים כלשהם, אז בסיום הקריאה:

הפונקציה מחזירה מערך ממוין של איחוד איבריהם.
למשתנה inv נוספו בדיוק מספר ההפכים בין איברי L לאיברי R (כלומר, מספר האיברים בL שגדולים מאיברים בR).

הוכחה: את החלק הראשון של המשפט הוכחנו כבר לגבי Merge, ולכן יש להוכיח רק את חלקו השני.

נניח שאחת משורות 4 או 9 בוחרת למזג את L[l]. בשלב זה, מספר האיברים שכבר נלקחו מR הוא r - 1, וכל אחד מאיברים אלה קטן בהכרח מL[l], או, במילים אחרות, מרכיב הפך בייחס לL[l]. מצד שני, כל איבר בR שעדיין לא נבחר, בהכרח גדול מL[l], ולכן אינו מרכיב הפך בייחס לL[l]. לכן כשנבחר L[l], הפונקציה מוסיפה לinv בדיוק את מספר ההפכים שהוא חלק מהם. היות שהפונקציה בוחרת בשלב כלשהו כל איבר מL, היא מוסיפה לinv את סך כל ההפכים בין L לR, בדיוק כפי שנטען.

כדי להשלים את הפתרון, פשוט נכתוב שוב פעם את Merge-Sort , אלא שבמקום לקרוא לMerge נקרא לMerge-Count-Inversions:

# Merge sort also counting inversions. 
# Takes an array (Values).
# Returns an array of the same elements, sorted in increasing order; also increases global variable inv 
# 	by the number of inversions.
Merge-Sort-Count-Inversions(Values)
1	if Length(Values) <= 1
2		return Values

3	mid = ⌊(1 + Length(Values)) / 2⌋
		
4	L = Merge-ּSort-Count-Inversions( Values[1, ... , mid] )
5	R = Merge-Sort-Count-Inversions( Values[mid + 1, ... , Length(Values)] )
	
6	return Merge-Count-Inversions(L, R)

לפני הקריאה הראשונה לMerge-Sort-Count-Inversions נאפס את המשתנה הגלובאלי inv. בסיום המיון, המשתנה inv יכיל את מספר ההחלפות, כפי שמראה המשפט הבא.

משפט:

בסיום המיון, המשתנה inv יכיל את מספר ההחלפות.

הוכחה: ההוכחה היא באינדוקציה על אורך המערך. נוכיח שבקריאה לMerge-ּSort-Count-Inversions במערך שארכו $\displaystyle n$ , מספר ההפכים במערך מיתוסף לinv.

(בסיס האינדוקציה) אם אורך המערך הוא 0 או 1, אז שורה 2 של IMerge-ּSort-Count-Inversions תצא ישר. inv לא ישתנה מערכו ההתחלתי של 0, בדיוק כפי שאמור להיות (אין הפכים במערך ריק או במערך בעל איבר יחיד).

(מעבר האינדוקציה) נניח שאורך המערך גדול (ממש) מ1. יש שלושה סוגי הפכים אפשריים במערך:

הפכים בין איברים בחציו השמאלי לבין עצמם
הפכים בין איברים בחציו הימני לבין עצמם
הפכים בין איברים בחציו השמאלי לבין איברים בחציו הימני

כל אלו בהכרח מחושבים נכון:

הפכים בין איברים בחציו השמאלי לבין עצמם מיתוספים נכון (עפ"י הנחת האינדוקציה) בשורה 4 של Inversions-Imp.
הפכים בין איברים בחציו הימני לבין עצמם מיתוספים נכון (עפ"י הנחת האינדוקציה) בשורה 5 של Inversions-Imp.
הפכים בין איברים בחציו השמאלי לבין איברים בחציו הימני מחושבים נכון בפונקציה Merge-Count-Inversions, כפי שהוכחנו קודם. אמנם הפונקציה אינה נקראת על חלקי המערך המקוריים, אלא על פרמוטציות שלהם (שהרי 4 ו5 ממיינות אותם), אך לפרמוטציות בהכרח אותו מספר ההפכים אחד בייחס לשני.

קל לראות שהאלגוריתם עובד בזמן $\displaystyle n\cdot \log(n)$ - ההוכחה זהה לזו של ניתוח הסיבוכיות במיון מיזוג.

6

נסמן את זמן הריצה של Alg(A, i, j) כ $\displaystyle T(i,j)$ .

נצייר את עץ הפרישה של הפונקציה:

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

נפתור $\displaystyle n^{\frac {1}{2^{h}}}=k$ , ונקבל

$\displaystyle {\frac {\log(n)}{2^{h}}}=\log(k)\Rightarrow 2^{h}={\frac {\log(n)}{\log(k)}}\Rightarrow h=\Theta (\log \log(n))$ .

הסיבוכיות, לכן, היא $\displaystyle \Theta (n\cdot \log \log(n))$ .

7

נתבונן בעמודה האחרונה, ונספור את מספר ה0-ים ומספר ה1-ות שאנו רואים. היות שיש $\displaystyle m=2^{n}-1$ , שורות, אז מספר ה0-ים גדול ב1 ממספר ה1-ות, או הפוך. נניח שמספר ה0-ים גדול ב1 ממספר ה1-ות (המקרה השני סימטרי). נוכל להסיק שני דברים:

הספרה החסרה בעמודה זו היא 1.
עלינו להתמקד רק בשורות בהן הספרה בעמודה זו היא 1 (קומבינטורית, לא ייתכן אחרת).

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

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

Print-Missing-Number(M)
1	n = Num-Cols(M)

2	Rows = Make-Stack()

3	for j in [1, … 2^n - 1]
4		Insert-Front(Rows, j)
	
5	for i in [1, … n]
6		Zeros = Make-Stack()
7		Ones = Make-Stack()
	
8		while Size(Rows) &gt; 0
9			row = Pop(Rows)
		
10			if M[row][i] == 0
11				Push(Zeros, row)
12			else
13				Push(Ones, row)
			
14		if Size(Zeros) &gt; Size(Ones)
15			Print(1)
16			Rows = Ones
17		else
18			Print(0)
19			Rows = Zeros

1-4 מאתחלות את המחסנית Rows כך שתכיל את כל (מספרי השורות). 5-19 עובורת על כל העמודות. בכל איטרציה, 8-13 מחלקות את מספרי השורות בRows לשתי מחסניות, לפי ערך ביט העמודה הנכחית. 14-19 מדפיסות את הביט החסר בעמודה הנכחית, ומחליטות באיזו משתי המחסניות להתמקד.

נותר לנתח הסיבוכיות. נשים לב שהאיטרציה הראשונה פועלת בזמן $\displaystyle \Theta (m)$ , האיטרציה השניה בזמן $\displaystyle \Theta (m/2)$ , ובאופן כללי, האיטרציה ה $\displaystyle i$ בזמן $\displaystyle \Theta (m/2^{i})$ . זמן הריצה, לכן, הוא $\displaystyle \sum _{i=1}^{n}\left[\Theta (m/2^{i})\right]=\Theta (m).$

8

נוכיח באינדוקציה שקיים $\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$ גדול מספיק.

9

נשתמש בעץ פרישה. ברמה הראשונה יש צומת יחיד, והוא תורם $\displaystyle f(n)$ . ברמה השניה יש $\displaystyle a$ צמתים, וכל אחד מהם תורם $\displaystyle f\left({\frac {n}{b}}\right)$ . ברמה ה $\displaystyle i$ (בהנחה שהרמה הראשונה היא ב $\displaystyle i=0$ ), יש $\displaystyle a^{i}$ צמתים, וכל אחד מהם תורם $\displaystyle f\left({\frac {n}{b^{i}}}\right)$ . אנו יודעים שגובה העץ הוא $\displaystyle h=\Theta (\log _{b}(n))$ . נפשט: $\displaystyle \sum _{i=0}^{h}\left[a^{i}\cdot f\left({\frac {n}{b^{i}}}\right)\right]=$
$\displaystyle \sum _{i=0}^{h}\left[a^{i}\cdot \Theta \left(\left({\frac {n}{b^{i}}}\right)^{\log _{b}(a)}\cdot \log ^{k}\left({\frac {n}{b^{i}}}\right)\right)\right]=$
$\displaystyle \Theta \left(\sum _{i=0}^{h}\left[a^{i}\cdot {\frac {n^{\log _{b}(a)}}{b^{i\cdot \log _{b}(a)}}}\cdot \log ^{k}\left({\frac {n}{b^{i}}}\right)\right]\right)=$
$\displaystyle \Theta \left(\sum _{i=0}^{h}\left[a^{i}\cdot {\frac {n^{\log _{b}(a)}}{a^{i}}}\cdot \log ^{k}\left({\frac {n}{b^{i}}}\right)\right]\right)=$
$\displaystyle \Theta \left(n^{\log _{b}(a)}\sum _{i=0}^{h}\left[\cdot \log ^{k}\left({\frac {n}{b^{i}}}\right)\right]\right)=$
$\displaystyle \Theta \left(n^{\log _{b}(a)}\sum _{i=0}^{h}\left[\left(\log(n)-i\cdot \log(b)\right)^{k}\right]\right)=$
$\displaystyle \Theta \left(n^{\log _{b}(a)}\log(b)^{k}\sum _{i=0}^{h}\left[\left({\frac {\log(n)}{\log(b)}}-i\right)^{k}\right]\right)$
נשים לב שעפ"י חסמי האינטגרלים לטורים,‏ $\displaystyle \sum _{i=0}^{h}\left[\left({\frac {\log(n)}{\log(b)}}-i\right)^{k}\right]=\Theta \left(\log ^{k+1}(n)\right)$ .