Herzlich willkommen! Wir haben heute zwei Dinge vor. Zum einen einen Nachtrag vom letzten Mal,

wo ich den Autoren eine ihrer Behauptungen nicht geglaubt hatte. Ich glaube sie mittlerweile schon.

Damit könnte man also die Abschätzungen, die die Autoren eine Behauptung angeben,

sogar um einen zu verbessern. Und weil der Beweis ganz schick ist, dachte ich,

ich präsentiere ihn dann doch mal. Er dauert auch nicht lange.

Erinnern wir uns an die Behauptung. Die Behauptung war folgendes, es geht nur um natürliche Zahlen.

Also im Moment braucht also niemand irgendwas über Informatik zu wissen. Wir machen also

reines Rechnen mit natürlichen Zahlen. Die Behauptung ist diese. Also einmal haben wir hier

diesen Term n mal ceiling von log n minus zwei hoch ceiling von log n plus eins. Das war der Term,

den wir in einer Induktion als obere Schranke eingesehen hatten für die Anzahl cn der Vergleiche,

die wir maximal brauchen, wenn wir eine Sequenz mit Merge Sort sortieren. So und die Behauptung war

diese hier. Das ist kleiner gleich n mal log n ohne irgendwelche Rundungen. Was man sehr schnell

sieht, ist, dass das kleiner gleich n mal ceiling von log n ist. Damit hatten wir uns letztes mal

zufrieden gegeben und wir wollen diese Abschätzung verschärfen auf n mal log n. Das ist also bis zu n

mal weniger. Und wenn man das gezeigt hat, dann hat man also als Abschätzung, ein besser als es im

Buch steht, dass c von n kleiner gleich floor von n mal log n ist. Warum? Naja, c von n ist eine

ganze Zahl und sie ist dann hier nach kleiner gleich n mal log n, also insbesondere kleiner gleich floor

von n mal log n. Gut, ja wie zeigt man das? Ja, erstmal versagt man sich ein paar Bezeichnungen

für log n und bzw. genauer gesagt für ceiling von log n. Wenn ceiling von log n gleich k ist,

dann heißt das folgendes. Moment, das soll sein eine Äquivalenzumformung. Also ich forme das

gleich äquivalent um. Also äquivalent Doppelpunkt für. Das hier ist eine Situation, in der ceiling von

log n gerade k ist. K minus 1 ist es nicht, weil 2 hoch k minus 1 kleiner als n ist. 2 hoch k

dagegen ist größer gleich n, also ist ceiling vom log gerade k. So und jetzt formieren wir das

äquivalent um und zwar indem wir beide Seiten, wie sagt man das, als als Exponenten über 2 nehmen.

Also äquivalenterweise ist also 2 hoch linke Seite kleiner gleich 2 hoch rechte Seite. Wir

exponentieren beide Seiten aber mit 2 nicht mit e. So was passiert dann?

Für das hier also k gleich ceiling von log n gilt. Ja was passiert? Also ich habe hier auf

der linken Seite eine 1. Gut exponentieren mit 2 macht daraus ein Faktor 2. So 2 mal. So was

habe ich noch? Ich habe n mal log n, also n mal k. Gut kann man nichts dran machen, das wird 2 hoch

n mal k natürlich als Faktor. Beim exponentieren werden aus so manchen Faktoren. So dann habe ich

noch dieses minus 2 hoch ceiling von log n, also minus 2 hoch k, das bringe ich mal auf die rechte

Seite. So und bin ich hier also fertig und ich habe zwei Terme auf der linken Seite verarbeitet,

habe noch zwei auf der rechten über. So ich habe also gerade 2 hoch k nach rechts gebracht,

exponentieren macht daraus 2 hoch 2 hoch k und dann habe ich noch das was schon recht stand n

mal log n. Wenn ich das, wenn ich 2 hoch n mal log n nehme, dann kann ich das log n runterziehen,

dann wird das n. Also 2 hoch log n ist ja per Definition gerade n. Also habe ich hier n hoch n.

So nicht? Das ist also durch exponentieren äquivalent umgeformt, diese Ungleichung

da oben. So und das Ding, das beweisen wir durch Induktion über k. Ja, wo fangen wir an? Wir

fangen an bei k gleich 0. Ja was passiert dann? Dann haben wir hier 2 hoch 0, also 1, also 2 mal

1. Was bekommen wir hier? 2 hoch 0 ist 1, also 2 hoch 1 gleich 1 mal, naja n hoch n bleibt n hoch n.

Ja gut, das ist auf jeden Fall richtig. N muss sowieso mindestens 1 sein, sonst klappt das alles

nicht. Also sonst wir den Logarithmus da ja gar nicht hinschreiben dürfen. Das heißt hier haben

wir dann mindestens 1 hoch 1 und ab 1 hoch 1 stimmt es für 2 auf 2 erst recht und so weiter.

Das ist also richtig. Gut. Okay, ja das war der weniger überraschende Teil.

So, Induktionsschritt von k minus 1 nach k. Gut, wir fangen einfach an das Ding abzuschätzen.

2 mal 2 hoch n mal k. So nun kommt eben der Kasis knacklis an diesem Beweis. Wir wollen

jetzt ausnutzen die Induktionsvoraussetzung. Die Induktionsvoraussetzung ist dieselbe Aussage

für k minus 1. Nun müssen wir uns aber angucken, früher gab es Zeigestücke in solchen Sälen,

also wir müssen uns angucken da oben diesen Bereich von n, für den die Aussage dann gilt.

Wenn wir also jetzt die Induktionsvoraussetzung für k minus 1 anwenden wollen, müssen wir auch n