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):
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?
