[Algorithmen] asymptotischer Aufwand von rekursiver Formel

[xenobyte]

Moin,

ich habe folgende rekursive Formel

T(N) = 2 * T (N - 1) + 1 wobei T(0) = 0

Ich sondiere:

T(1) = (2 * 0) + 1 = 1

T(2) = 2 * 1 + 1 = 3

T(3) = 2 * 3 + 1 = 7

T(4) = 2 * 7 + 1 = 15

T (5) = 31

T (6) = 63

Problem: Die Formel für den asymptotoschen Aufwand lautet

T (k) = 2^k − 1 = O(2^k )

aber ich kann leider nicht nachvollziehen wie man darauf kommt. Hat jemand nen heißen Tip?

[GoodFella]

vielleicht hilft dir das:

T(n) = 2 * T(n-1) + 1; Abbruch: T(0)=0


Bsp: T(4)
---------

T(0) = 0
T(1) = 2 * T(0) + 1
T(2) = 2 * T(1) + 1
T(3) = 2 * T(2) + 1
T(4) = 2 * T(3) + 1

einsetzen:

T(4) = 2 * (2 * (2 * (1) + 1) + 1) + 1


Distributivgesetz:

2 * (1)               + 1 = 2*1 + 1 =                    2^1 + 2^0

2 * (2*1 + 1)         + 1 = 2*2*1 + 2*1 + 1 =            2^2 + 2^1 + 2^0

2 * (2*2*1 + 2*1 + 1) + 1 = 2*2*2*1 + *2*2*1 + 2*1 + 1 = 2^3 + 2^2 + 2^1 + 2^0


http://de.wikipedia.org/wiki/Geometrische_Reihe

.. hab mich bestimmt irgendwo vertan, kommt was anderes raus :P

[dumm']

I.B. T(0) = 0
I.S. T(n+1) =(Def.)= 2 * T(n) + 1 =(I.H.)= 2*(2^n - 1) + 1 = 2^(n+1) - 2 + 1 = ...

Hier zwar nicht notwendig, aber tendenziell unabdingbar: http://en.wikipedia.org/wiki/Master_theorem