Video 3-8: Die Rekursionsbaum-Methode

0:04 Also als Nachtrag zu dem Kapitel letztes Mal, indem ich Ihnen das Ergebnis vorweggenommen hatte, was das Master Theorien besagt, möchte ich noch mal ein Beispiel von der Rekursion mit ihnen lösen, ohne das Master Theorem direkt zu verwenden, sondern als als Vorbereitung und Motivation, warum so ein Ergebnis äh möglich ist oder Sinn ergeben kann. Wir hatten schon uns Merchort angeschaut und äh sie erinnern sich an die Art von Rekursionen, die da die wir da untersuchen, sind diese Divide and Conquer Rekursionen, die eben daraus entstehen, dass wir eine Eingabe in mehrere gleich große Teile aufteilen, auf denen wir rekursiv den gleichen Algorithmus aufrufen. Die Teilprobleme müssen wir dann irgendwie kombinieren zu einer Gesamtlösung, was dann immer eine Rekursion von dieser Art gibt, wobei eventuell diese Werte, die hier bunt gedruckt sind, einen anderen Wert haben können im Allgemeinen. Und für Merchsort hatte ich Ihnen so ganz ganz ähm äh mit viel Händewedeln versucht nahezulegen, dass man da äh vielleicht sowas rausbekommt, wie ein Beitrag von n für jedes Level in diesem in dieser Zeichnung mal der Anzahlvel, die man hier bekommt.

1:20 Das schauen wir uns jetzt gleich noch mal ähm allgemeiner an. Nur zur Erinnerung, ähm ich würde das quasi hier dazwischen schieben. Das ist die allgemeine Form von Rekursionen, um die es in diesem Kapitel gehen soll. Also ein T von N ist definiert als eine rekursiven Aufruf auf kleineren Eingaben. B muss immer größer als 1 sein und davon mache ich aber A Stück. So wie bei Merch A und B beides zwei war, kann aber im Allgemeinen verschiedene Zahlen sein und ich habe irgendwelche Kosten, um die Teilprobleme oder die Lösung der Teilprobleme zu kombinieren. Das könnte im Allgemeinen irgendeine Funktion sein, die auch wiederum für größere Eingaben mehr Aufwand macht. Bei Merch war das einfach n als lineare Kosten, aber kann auch hier allgemeiner sein.

2:12 Und hier möchte ich ein ein anderes Beispiel mal noch von Hand machen, bevor wir mit dem Master Theorien dann weitermachen, obwohl sie das in Zukunft verwenden dürfen.

2:34 Die Rekursion ist jetzt nicht direkt aus irgendeinem Algorithmus motiviert, sondern einfach nur die fällt jetzt als Definition vom Himmel. Die ist so gewählt, dass wir ein paar Sachen in der Rekursion sehen können, nicht, dass sie jetzt irgendwie eine Anwendung per se hätte.

2:57 belasse es mal in dieser Schreibweise. Wir können dann gleich drauf zurückkommen, ähm wie wir das sonst handhaben wollen. Sagen wir hier mal eins. Also, das könnte eine Rekussion sein, die die Laufzeit von dem Algorithmus beschreibt. In den Farben von oben hätte ich a rekursive Aufrufe der Größe B. Das hier müsste also irgendwie grün sein und das hier blau. Werde ich dann im weiteren Verlauf nicht weitermachen, sonst wären wir glaube ich nicht fertig. Ich habe kein lila, dann kann ich nur pink machen und der ähm Basisvol orange.

3:43 Wie könnte man so eine Rekursion lösen, wenn man nicht direkt das Masterheorem schon irgendwie als gottgegebene Lösung bekommt? Ähm, die die einzige Methode, die ich Ihnen auch letztes Mal schon bisschen angeteasert hatte, war einmal die Rekursion einsetzen und gucken, was passiert. Und an dieser Stelle ähm eine allgemeine Methode für diese Art von Rekursion ist das ein bisschen grafisch zu machen. Das ist letztlich nichts anderes als die Rekursion ausfalten, aber es ist ein bisschen geschickter visuell aufgeschrieben. Das ist die Rekursionsbaummethode da ist die Idee, wir schauen uns an, was die Gesamtkosten dieser Rekursion am Ende ergibt. Und die einzigen echten Kosten sind ja immer diese Leanen. Das andere ist nur irgendein rekursiver Aufruf. Da verschiebe ich ähm die Kosten in in zukünftige Aufrufe, aber wirklich bezahlen muss ich immer diesen lillanen Teil. Also haben wir für den obersten Aufruf und an der Stelle m an der Stelle benutzen wir jetzt noch das Wissen, was uns dieses Theta von n² gibt. Das ist noch mal Wiederholung von äh letzter Woche. Das waren diese asymptotischen Approximationen.

5:09 Das Thet von n besagte ja eine obere und untere Schranke für das n das für die Funktion hier in Abhängigkeit für diesem n Quadrat. Also unsere Funktion feder im allgemeinen Stand, die ist also in groß O von N² und in klein O. Okay, schreib das hier mal noch der Mengenschreibweise, dann hat's den Effekt, dass ich hier ähm die Schnittmenge bilden kann. Ich habe letztes mal kurz erwähnt und sie werden es noch in dem aktuellen Übungsblatt ein bisschen einüben. Diese groß von groß omegon, klein von und all diese Variationen von asymptotischen Approximation sind formal Mengen von Funktionen, nämlich allen, die in wenn man den Quenz, wenn man den Grenzwert bildet, den passenden Limis Superior haben oder den die passende beschränkte Beschränktheit von den Grenzwert von den Quotienten haben. Und über solche Mengen von Funktionen kann ich natürlich auch dann z.B. Schnittmengen bilden. Dementsprechend ist das f eine Funktion, die sowohl in groß von n² ist, als auch in groß Omega von n².

6:22 Das ist hier einfach bequemer, kürzer zu schreiben. Äh, das hieß ja aber insbesondere, dass es eine Konstanten. Es gibt ein C1 und ein C irgendwelche reellen Zahlen im allgemeinen, sodass unsere Funktion zwischen C1 mal n² und n quadrat und c mal n² äh eingepackt ist, sofern das n genügend groß ist. Ja.

7:15 Und für diese Rekursion hier werden wir letztlich ähm zwei zwei Rechnungen machen müssen, wenn wir die präzise Lösung wollen. Einmal eine obere Schranke und dann eine untere Schranke. und wir werden es dann dabei belassen zu zeigen, dass die sich nur um eine Konstante unterscheiden. Ähm im Masterheorem ist das Ergebnis hier ja auch immer nur so ein eine Thetak Klasse gewesen. Das heißt, es ist eine obere und eine untere Schranke, die sich aber um eine Kon um konstanten Faktor unterscheiden können.

7:58 Also schauen wir uns hier erstmal nur eine obere Schranke an. Dementsprechend ersetzen wir immer wieder neue seltsame äh Vorkommnisse, dass er sozusagen, na ja, die die Nerdvion ist, der schaut sich den Fenstertitel an, der ändert sich, wenn man eine Datei öffnet. Äh, wenn er aber das Fenster schon offen hat, hat er das ignoriert. Na gut, braucht sie nicht kümmern. Ich ersetze jetzt hier diese Funktion durch diese obere Schranke und wir tun mal einfach so, als würden wir nur für diese obere Schranke die Rekursion lösen. Dadurch bekommen wir am Ende eine obere Schranke für die Lösung der echten Rekursion, weil alle Terme, die wirklich was kosten, sind hier diese lilanen und jeden davon beschränken wir nach oben. Das heißt, das Gesamtergebnis ist auch eine obere Schranke für unser T von N.

9:12 Warum es mir geht, ist der Rekursionsbaum. Wir haben einen ersten Aufruf T von N, der generiert uns Kosten C* N². Das ist der äh der nicht rekursive Teil. Dann mache ich drei rekursive Aufrufe in diesem Fall. Ja, und jeder von denen ist auf einer um Faktor 4 kleineren Eingabe jetzt. Das heißt, für diesen rekursiven Aufruf bekomme ich jeweils wieder den diesen lillanen Aufwand, aber eben n jetzt durch n durch dur 4 ersetzt. Das heißt, hier bekomme ich c* n dur 4². Hier bekomme ich noch mal c* n dur 4 quadrat. Ja, diese witzigen Dinge, das ist eine 4. C mal n durch 4 zum Quadrat.

10:07 Und dann kann man das natürlich vereinfachen. Das ist dann äh 3 in Summe 3 mal schreiben wir das mal auf Einbruch. Die 4 Quadrat W 16.

10:24 Das C bleibt davor und n quadrat. An der Stelle sieht man schon so ein bisschen, der Aufwand hier oben ist c mal n quadrat. Hier habe ich das gleiche, aber mit einem deutlich kleineren Faktor vorne dran. 316 ist ja äh deutlich kleiner als eins.

10:45 Wenn ich das Ganze noch einen Schritt mache, also jeder dieser rekursiven Aufrufe generiert wieder drei rekursive Aufrufe. Sie sehen, äh wir werden das nicht sehr viel weiter machen, weil das doch dann relativ äh schnell den Platz eng macht.

11:08 Dann bekomme ich hier C* N= 16 zum Quadrat, weil ich jetzt die n viel noch mal durch vier teilen muss und hier auch CN durch 16 zum Quadrat und so weiter und so fort.

11:46 ähm was wir hier einsetzen ist immer diese das Quadrat kommt von diesem von der lilanen Funktion von dem fleem wir immer durch vier teilen. Aber die Kosten, die dieser rekursive Aufruf an der Stelle tatsächlich verursacht, abgesehen von dem Teil, den erweitert, der Baum würde ja noch weitergehen, ja, aber mir geht dann die Lust aus, die alle zu malen. Ähm, die rekursiven Kosten hier, die hängen dann wieder von dem n ab, aber die die tatsächlichen Kosten in dem Schritt sind quadratisch in der Teilproblemgröße und das ist das n dur 16 oder vielleicht hätte ich n dur 4 quadrat hier schreiben sollen, um das Muster deutlicher zu machen. Wenn wir auch hier wieder zusammenzählen, dann haben wir jetzt seh mal wie viele Aufrufe habe ich hier, wie viele Teilprobleme diese auf diesem Level habe ich.

12:44 neun Stück, also 3 zum Quadrat, ne? Ich habe immer hier verdreifacht und dann noch mal verdreifacht. Und meine Eingabe ist aber um 4 Quadrat geschrumpft. Und dann mache ich das noch mal zum Quadrat für ähm den Funktionsaufruf und hinten dran kommt das eigentliche n Quadrat. äh wobei hier n immer gemeint ist die ursprüngliche Größe. Also, ich habe keinen Namen für diese Teilprobleme hier für die Größe der Teilprobleme definiert. Das ist einfach ursprüngliche Größe geteilt durch einen Faktor.

13:25 Okay, das ist also eine noch kleinere Zahl, mag man schon gar nicht mehr ausrechnen. Ähm, Also was man hier sieht ist, dass wir in jedem Level, dass wir absteigen, einen konstanten Faktor an Kosten verlieren. Das oberste Level kostet uns CN². kann wir ja auch noch mal an den Rand schreiben, damit wir die hier untereinander stehen haben. Das levelt runter schon einen Faktor, der echt kleiner als ein ist weniger. Und den Faktor den den exponenieren wir jedes Mal, wenn wir ein Level runtergehen. Das heißt, der Kostenbeitrag, der wird immer kleiner. Das sieht man anschaulich an der Stelle schon. Wenn man das systematischer aufschreiben will, dann würde man das über die Level aufsummieren. Also, das geht ja, der Baum geht weiter. Am Ende würden wir gerne eine Summe über alle Level bilden. Dafür müssen wir aber wissen, wie viele Level das insgesamt gibt.

14:47 Und der Punkt ist, der Baum geht nicht unendlich weiter. An irgendeiner Stelle komme ich zu Teilproblemen, wo mein n hier, also schlampig könnte man sagen, konstant groß ist. Aber da die Rekursion hier bis ähm bis 1 geht, irgendwann komme ich zu einem Teilproblem, was Größe 1 hat.

15:08 Und von denen habe ich natürlich ganz ganz viele. Das heißt, auf diesem allerletzten Level, da habe ich den orangenen Beitrag und der ist hier in der Konstante 1.

15:31 Aber wie viele von diesen Aufrufen auf unterstem Level habe ich denn? Das ist auch noch was, was wir uns überlegen müssen. Also auch die Ansen einsen sollten eigentlich orange sein.

16:05 Und Kern für die Analyse ist jetzt diese zwei Parameter. Wie hoch ist der Baum und wie viele Blätter gibt es auf dem untersten Level?

16:12 Für die Höhe vom Baum haben wir schon relativ klaren Hinweis, denn das n wird in jedem Schritt um ein Faktor 4 kleiner. Das kann ich nicht beliebig lang machen, bevor ich kleiner als 1 bin. Und für diesen Teil hier nehmen wir der Einfachheit halber wieder an, dass n eine exakte Vierer Potenz ist.

16:41 Dann geht es auch glatt auf und ich muss mich nicht drum kümmern, was passiert, wenn hier ähm eigentlich Rundungen vorzunehmen sind. In dem Algorithmus für Teilprobleme würde man ja immer runden müssen.

16:51 Sortieren von sieben Elementen macht keinen Sinn. Ähm letztes Mal schon angeteasert, für diese Rekursion ignorieren wir das und ich zeige Ihnen im Nachhinein ein Kriterium für die Rekursion. dass das beweist, dass es äh okay ist, dass man sozusagen die asymptotische Wachstumsrate der Lösung nicht verändert, indem man das Runden weglässt oder ignoriert oder äh auf äzen beschränkt, auf denen das Runden ähm nicht vorkommt.

17:32 n ge 4 hoch den die Zahl des Levels, wenn wir hier mit 1 anfangen, mit 0 anfangen, ne? Hier ist ein Z und dann geht es weiter bis zu einem bestimmten Level. Na ja, genau. Bis dann. Ah, was ist denn los?

18:05 Genau. Dann, wenn das hier eins ist, hören wir auch. Das sind die ähm das ist das niedrigste Level hier und dafür müssen wir nach L auflösen. Also bringen wir die 4 hoch L auf die andere Seite, ne?

18:34 Die Umkehrfunktion für den für das Exponentzieren ist der Logarithmus. Das heißt, die Anzahl Level ist gerade der Logarithmus zur Basis 4 von n. Jetzt kann man sch das +- 1 streiten, weil hier das jetzt das maximale der maximale Level Index ist. Der hat aber bei null angefangen zu zählen. Also es ist eigentlich ein Level mehr, aber da kommt das für die Asymptotik auch nicht drauf an. Die Anzahllevel ist also logarithmisch in n und die Basis ist die 4, die ähm aus der allgemeinen Form blau war. Das ist die der Schrumpfungsfaktor für die Teilprobleme. Jetzt können wir auch die Anzahl Level im Baum äh uns überlegen.

19:28 Nach diesen Log zur Basis 4 von N leveln habe ich ja in jedem Schritt meine Anzahl Knoten hier in diesem Baum verdreifacht. Von jedem Schritt zum nächsten hat jeder dieser [räuspern] Knoten hier drei Kinder äh beigesteuert.

19:47 Das heißt, die Anzahl Blätter ist 3 hoch die Anzahl Level, die wir runtergehen. Das maximale Level ist unser Logis 4. Ja, und das ist jetzt so eine korrekte Lösung. Diese aber ein bisschen unbequem äh in dieser Form auszudrücken. Das heißt, wir formen die ein bisschen um und dann machen wir uns zu Nutze, dass man die Logarithmen umschreiben darf.

20:26 Also z.B. kann ich ja diesen Logarithmus auf Basis 3 um Münzen, dann hätte ich das hier geteilt durch log 3 von 4. Soweit ist es das gleiche. Und dann mache ich Potenzgesetze weiter. Äh wenn ich einen Produkt in der Potenz hab, dann kann ich die erst ein der Teil der Potenz ausrechnen und einen Faktor als Potenz nach außen ziehen. Das heißt, ich nehme jetzt hier diesen Teil von die beiden zusammen, die packe ich in die Klammer und dann ist 3 hoch log zur Basis 3 ist einfach wieder n.

21:18 Und was übrig bleibt ist log von 1 durch das hier. Das kann ich jetzt noch mal oben schreiben, damit ich diese diesen Kehrwert loswerde, ne? Oder nicht?

22:05 ist eine Formel, die sich vielleicht die sich vielleicht gemerkt haben. Ne. Gut, steht glaube ich sogar so auf dem Cheat Cheat. Gut, das heißt, die Anzahl Blätter kennen wir jetzt auch. Dieses letzte Level steuert also was bei 1 mal das hier n hoch eine Konstante, über die wir jetzt nicht besonders viel wissen, aber zumindest ist sie ähm Das heißt, die Anzahl Blätter ist hier relativ klein und der Grund anschaulich ist diese äh durch vier Teilen reduziert die Größe von den Teilproblemen viel viel schneller, als wir mit dem Faktor 3 an äh Knoten produzieren hinterherkommen. Also insbesondere ist hier über diese Level aufsummieren. Der ganze lillene Teil hier, der steuert irgendwas in n Quadrat bei mit irgendwelchen Faktoren davor, während die Blätter hier nur einen Beitrag liefern von diesem n hoch 0,8 deutlich weniger.

23:34 Jetzt kann man noch normal die die Level aufsummieren als obere Schranke. Also wir haben das Summer über die Levels Da hatten wir als Gesamtkosten immer dieses die das C ziehe ich mal raus. Dann hatten wir 316 hoch L. Ja, hier kein 316. hier 1, dann Potenz 2 mal unser n Quadrat. Das kann man natürlich auch vor die Summe vor die Summe ziehen. Das wenn es eh noch mal aufschreiben müssen, lass wir das C noch in das ist klarer. Also, das ist der Magenta Teil und wie schon gesagt, der äh der Teil für die Blätter, der steuert nur diesen Teil hier bei.

24:53 Das heißt, für die für das asymptotische Wachstum ist das hier deutlich wichtiger, weil es die höhere Potenzi hat. äh werden sie in den Übungen auch noch im Detail ähm nachrechnen für diese Art von Funktion.

25:05 Wie man jetzt hier zu einem zu einem weiteren Ergebnis kommt, ist auch äh immer wieder ein ähnlicher Trick, deswegen wollte ich den einmal auch ausführlich zeigen. Diese Summe hier, die könnte man ähm nach Cheat Sheet auch direkt auflösen. Der erste Schritt ähm ist vielleicht noch ohne Abschätzung. Ich kann das C mal n² vor die Summe ziehen, weil das gar nicht von L abhängt.

25:36 Das ist ein N. Und dann habe ich hier dieses 316 hoch L und das bleibt bestehen. Und diese Summe hier, die kann ich entweder nach Cheat Sheet versuchen zu lösen, dann habe ich diesen Logarithmus noch drin oder wir machen es uns bequem und schätzen die nach oben ab. Dann ist es einfach ähm statt hier aufzuhören, summiere ich bis unendlich weiter.

26:15 Und diese Summe hier wiederum ist eine geometrische Reihe, kennen Sie vielleicht auch auswendig. die geschlossene Form davon oder der Wert der Reihe [schnauben] ist 1 ge 1- den Teil, den wir exponenzieren.

26:34 Und das ist halt irgendeine Zahl, die äh die kann man natürlich dann hier ausrechnen. Also was haben wir hier? 1 durch 131, also 163 und das gibt also einen konstanten Faktor zusammen mit dem C, aber im Wesentlichen ist die Funktion bestimmt von diesem n Quadrat.

27:03 Deswegen ist das ganze hier am Ende groß Uhr von N². Das war eine obere Schranke. Man könnte genauso eine untere Schranke rechnen, indem man hier ganz am Anfang nicht mit dem C anfängt, sondern mit dem C1. Aber wie Sie vielleicht sehen, ändert sich dadurch genau gar nichts, außer dass wir am Ende ein C1 und kein C bekommen. Das heißt, da brauche ich mir die Rechnung äh nicht noch mal antun. Das zeigt Ihnen auch, warum die die Lösung von dieser Art von Rekursionsgleichung in der Regel immer eine obere und untere Schranke der gleichen Wachstumsrate gibt, nur dass äh die Konstante ist anders. Das war die allgemeine Methode. Mit der Überlegung, wie sich die einzelnen Level auf diesem Baum verhalten, kann man diese Rekursion quasi immer knacken. Für diese spezielle Form von Funktionen, die wir hier aufgeschrieben haben, haben wir uns das halt hat sich jemand halt einmal überlegt, was da in allen Fällen passiert und aufgeschrieben, was das Ergebnis ist.

28:07 Diese Unterscheidung, die Fälle AB, B und C, das sind genau die Fälle, die hier den Unterschied machen, ob der dominante Beitrag vom allerersten Aufruf kommt. So wie in diesem Beispiel. Sie sehen, hier ist C* N² der Beitrag vom allerersten Aufruf. Und das war auch am Ende nach ein bisschen Rechnung im Wesentlichen das Wachstum der gesamten Rekursion. Was hätte noch passieren können? Äh eine Option ist, dass die Blätter dominieren. Es gibt viel viel mehr Blätter als die Kosten im obersten Aufruf. Das ist der letzte Fall im Master Theorie.

28:54 So, der erste Fall, der letzte Fall ist der, den wir hier hatten, dass der erste Teil dominiert. Der letzte Fall ist, die Blätter dominieren.

29:16 Der erste, weil hier ist erster Aufruf dominiert und der mittlere Fall ist, na ja, keins von beidem dominiert s die sind genau ausgeglichen. Jedes Level liefert etwa den gleichen Beitrag. Da hatten wir ein Beispiel gesehen in dieser Merchord Variante, da war das eben gerade so ähm austariert, dass was ich rekursiv verliere an n kompensiert wird durch das, dass ich mehr Aufrufe habe und dann liefert jedes Level den gleichen Beitrag. Dann muss ich das die Kosten pro Level multiplizieren mit der Anzahl Level.

29:56 Das ist der Grund, warum hier dieser Faktor log n dazu kommt. Das ist eigentlich ein log n zur Basis ähm von dem b, aber da das im groß Ohr steht und b eine Konstante ist, interessiert uns der Faktor nicht. Okay, lange Nachrede zum letzten Mal zu Master Theorem.

30:22 Das ist der allgemeine Rekursionsbaum, den habe ich letztes Mal übersprungen. Das ist das gleiche Bild, wenn man nicht direkt eine konkrete Rekursion einsetzt, sondern versucht das allgemeine Bild zu malen. Äh, dann bekommt man allgemein, was die Levelkosten, allgemein wie viele Blätter es gibt und allgemein wie hoch der Baum ist. Und im Wesentlichen geht aber die gleiche Rechnung dadurch, nur dass man die die Randfälle, welcher der Teil der Lösung dominiert, den muss man sich in Abhängigkeit von den tatsächlichen Zahlen überlegen. Ansonsten ist das Beispiel, wie ich es Ihnen jetzt vorget habe, ähm repräsentativ dafür, was man auch hier tun muss.

31:11 Ja, ich habe teilweise noch paar Sachen ergänzt. Äh, die kommen kommen dann sukzessive noch nach. Genau. Sie kriegen ja auch was ich ähm was ich hier aufschreibe äh steht als als Lecture Notes unten drunter auf der Vorlesung, aber auch eben mit Versatz dann ähm wenn ich nach der Vorlesung dann immer dazu komme.

31:35 Ähm Nachtrag zum Runden hatten wir letztes Mal ähm nur ganz kurz drüber gesprochen. Es gibt für die für die Profis sozusagen, die sich Gedanken darüber machen, ist es nicht geschummelt, dass man annimmt, dass n eine Potenz von B ist. Ähm gibt's eben dieses Kriterium, wenn unsere Funktion f äh dieses bestimmte Wachstumskriterium erfüllt, dann können wir allgemein beweisen, dass die Rundungen keinen Unterschied machen für die asymptotische Wachstumsrate des Ergebnis. Und insbesondere hier der wichtige Teil für sie ist das hier.

32:14 Wenn immer ihre Funktion f so aussieht oder diese äh diese Thetak Klasse hat von einem n hoch eine Konstante, was polynomial ist, ein Logarithmus hoch irgendeine Konstante und vielleicht sogar noch log hoch irgendwas. Ich weiß gar nicht, ob wir je ein Beispiel dazu haben, aber ja, sie dürfen diese Konstanten auch auf null setzen. Also alle Beispiele, die wir bisher hatten, fallen unter dieses äh Kriterium.

32:40 Wenn das gilt, dann brauchen wir uns über Runden keine Gedanken machen. Asymptotisches Wachstum bleibt gleich. Ähm, die Details davon müssen Sie nicht wissen, aber das war sozusagen ähm falls jemand weiterdenkt und sich fragt, warum wir da nicht schummeln, ist das sozusagen die Antwort. Aber die Details dazu brauchen Sie nicht in der Prüfung wissen. Markiere ich entsprechend mal noch.

33:09 Zweiter Teil, den Sie auch nicht für die äh Klausur wissen müssen, ist hier gibt's noch eine allgemeinere stärkere Version von so einem Master Theorem. Nur um Ihnen zu zeigen, dass man da mehr tun kann, wenn man ein bisschen mehr über die Funktion f weiß, also nicht nur eine Tetaklasse, sondern eine präzise Tilde Asymptotik. Dann kann man ähm noch ein allgemeinere Rekursion lösen, wo die verschiedenen Teilprobleme nicht alle gleich groß sind und man kann sogar von der Lösung am Ende auch eine Tilde Asymptotik bekommen, wo also die Konstante auch bekannt ist. Äh, wenn Sie das interessant finden, dann schauen Sie mal rein. Und wenn Sie es nicht interessant finden oder nur verwirrend finden, dann vergessen Sie die Folie einfach.