---

Geschrieben von Miakosa am 18.10.2019 um 12:25:

  Vom Algorithmus zur Rekursionsgleichung

Meine Frage:
Aufgabe:

Eingabe = n ? N (Natürliche Zahlen)

Ausgabe = keine

Algorithmus LINALG nicht rekursiv,liefert einen Wert vom Typ boolean und hat eine lineare Zeitkopmplexität

REKALG(n)

1 if n=1

2 then return

3 if LINALG(n)

4 then REKALG (?2n/3?)

5 else REKLAG(?n/3?)



a) Stellen Sie die Rekursionsgleichung zur Bestimmung der maximaleen Anzahl der rekursiven Auftrufe dieses Algorithmus mit dem Argument n auf. Zählen Sie die Auswertung der Anfangsbedinung auch als einen rekursiven Aufruf. ( Auf und Abrunden in der rekursionsgleichung vernachlässigen)

b) Lösen Sie die Rekursionsgleichung mit dem Master Theorems.



Meine Ideen:
mein Lösungsweg für a:
Ich habe erstmal für n ein paar werte eingesetzt:
n=1
Alg. beendet
n=2
LINALG (n)
then = 1

Alg. beendet
n=3
LINALG(3)
=2
Da n=2 und LINALG (3)
else = 1
Alg. beendet.

Ich bin mir nur jetzt unsicher ob ich den algorithmus so richtig verstanden habe und wie genau ich dadurch jetzt zur rekursionsgleichung komme.