Herr Gurin hat Ihnen ja letzte Woche nahegebracht, Komplexitätsabschätzung nicht nur der Schulmethode,

sondern auch der effizienteren Karatsuba Methode zur Multiplikation ganzer Zahlen.

Die Idee war, diese Algorithmen beide rekursiv darzustellen und dann für die Abschätzung

der Anzahl primitiver Operationen, die man jeweils braucht, sogenannte Rekorenzen herzuleiten,

wo also die Anzahl Operationen, die man für endstellige Zahlen braucht, abgeschätzt wird

durch einen Ausdruck, in dem wiederum die Anzahl primitiver Operationen, die man für

etwas kleinere Zahlen braucht, das war in einem Fall in halbe und in einem Fall eins

mehr, also in halbe plus eins jeweils aufgerundet.

Und es ist dann schon behauptet worden, dass aus diesen Rekorenzen eine Abschätzung in

geschlossener Form, also im Wesentlichen durch ein Polynom folgt.

Dafür steht der Beweis aber noch aus und damit werden wir uns heute beschäftigen.

Dass wir das machen, ist so ein bisschen redundant, weil wir später eine allgemeine Methode kennenlernen

werden, mit der man das also mechanisch machen kann.

Wir machen trotzdem vorher eine Rechnung von Hand, damit man so ein bisschen schätzen lernt,

was eigentlich dieses sogenannte Master Theorem, was wir dann später beweisen, für einen

Leistet.

Also Thema heute Rekorenzen lösen per Induktion.

Und ausdrücklich eben, wie gesagt, später machen wir das per Master Theorem.

So, wir brauchen unterwegs eine einfache Tatsache über endliche Summen von Potenzen,

sogenannte geometrische Reihen.

Das kennen Sie vermutlich aus Ingmat, aber ich wiederhole es einfach mal.

Also, Moment, da reiche ich jetzt von meiner Reihenfolge ab, also muss ich das suchen.

Hier.

Also, Erinnerung.

Geometrische Reihen.

Was ist eine geometrische Reihe?

Das ist was von dieser Form hier.

Ich nehme eine Zahl a und summiere ihre Potenzen auf.

Von 0 bis sagen wir mal k-1, damit die Formel gleich schöner aussieht.

So, für die Summierung dieser Dinger gab es einen Trick.

Ich meine, das ist natürlich eine endliche Summe, ich kann schlicht und einfach ausrechnen.

Ja, aber ich möchte gerne eine geschlossene Formel dafür haben, die keine Summe mehr involviert.

So, das war der Trick.

Der Trick war, ich nehme einmal diese Summe und multipliziere sie nochmal mit a.

Dann habe ich hier a hoch, fangen wir mit dem größten an, k, plus a hoch k-1.

Ist das eine Geheimderminologie?

Was ist genau die Terminologie?

Sie werden recht haben, dass der Ausdrucksumme ist.

Ja, die Reihe geht bis unendlich.

Also, wir multiplizieren mit a, das heißt dann ist der höchste Exponent k, dann kommt

k-1, plus und so weiter.

Und der kleinste ist dann 1, weil wir bei 0 anfangen und das nochmal mit a multiplizieren,

dann kommt also 1.

Da schreibe ich die ursprüngliche Reihe drunter, entsprechend sortiert und richtig eingeordnet

nach Potenzen, also plus und so weiter.

So, dann kommt hier nochmal a hoch 1 und wir haben ja aber angefangen bei a hoch 0, das

heißt hier kommt nochmal a hoch 0.

So, und dann subtrahiere ich das.

Ja, was kommt raus?

Ja, auch 0 ist 1, also schreiben wir hier gleich minus 1.