+1 Punkt
134 Aufrufe

Hallo zusammen,

ich muss in Theoretische Informatik folgende Rekurrenzgleichung lösen:

$$ T(n) = 2T(\frac{n}{3})+1 $$

aufgrund des Master-Theorems (aus unserem Vorlesungsskript):

mastertheorem.png 

Habe ich folgendes gemacht:

$$ T(n) = 2T(\frac{n}{3})+1 $$

$$ a=2, b=3, d=0 $$

$$ log_3(2) = \frac{log(2)}{log(3)}$$

$$ d < \frac{log(2)}{log(3)} => O(n^{log_b(a)}) $$

Aus diesem Grund:

$$ T(n) = O(n^{log_3(2)}) \approx O(n^{0,631}) $$


Ist das soweit korrekt?

von
Hallo, kann mir denn keiner helfen? Denn wenn das so richtig ist, mache ich die restlichen Aufgaben. Die sind ähnlich.

1 Antwort

0 Daumen

Ja, du hast das Master Theorem richtig angewendet! 

von

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
1 Antwort
0 Daumen
1 Antwort

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...