# Rekursionsformel für Laufzeit von Algorithmus



## Roydebatzen (20. Mai 2012)

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 (20. Mai 2012)

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 (20. Mai 2012)

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 (20. Mai 2012)

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?


----------

