Rekursionsformel für Laufzeit von Algorithmus

[Roydebatzen]

Hi,
Ich soll für folgenden Algorithmus die Laufzeit der Rekursionsformel bestimmen:

// Rueckgabewert true = Duplikat-frei
boolean checkDups(a) {
if (a enthaelt nur ein Element) {
return true;
}
aLeft = linke Haelfte von a;
aRight = rechte Haelfte von a;
if (!checkDups(aLeft) || !checkDups(aRight)) {
return false;
}
for (x in aLeft) {
for (y in aRight) {
if (x == y) {
return false;
}
}
}
return true;
}

Das Array soll die Länge n haben.

Ich hab leider keine Ahnung was die Logik dahinter ist,
aber ich würde sagen, dass die zweite If-Anweisung die Laufzeit 2*T(n/2) hat, falls n > 1.

und für die For-Schleife hört es schon auf.
Ich denke sie wird ja für je n/2 aufgerufen, also n/2*n/2 und dann halt mal dem Faktor der unterschiedlich ist. Also ist es doch T(n²/4) oder nicht?

Daraus würde dann folgen: T(n)=2*T(n/2)+T(n²/4)

Ist das richtig?

 

[AquaBall]

Wenn du suchst bevor du postest, dann findest du die Antwort!

(Macht sich nicht mal die Mühe 3 Zeilen weiter zu lesen, ärgerlich)

 

[Fant]

Es müsste n^2/4 statt T(n^2/4) heißen, denn dort hast du doch keinen weiteren rekursiven Aufruf, sondern es wird einfach nur "ganz normal" die for-Schleif durchlaufen...

Gruß Fant

 

[Roydebatzen]

Hey,

ja Danke, ich hatte es auch schon als erledigt markiert als ich es denn auch gesehen hatte. Hab erst nur bei google geluschert und nichts gefunden.

Aber denn erst recht:

Die O-Notation O(n) wäre denn ja:

n²/4+2*T(n/2) <= n²+T(n)<=n²+n=O(n²) oder nischt?