Lösen der Wiederholung T (n) = 3T (n-2) mit iterativer Methode

Es ist schon eine Weile her, dass ich eine Wiederholung lösen musste und ich wollte sicherstellen, dass ich die iterative Methode zur Lösung dieser Probleme verstehe. Gegeben:

Mein erster Schritt bestand darin, Begriffe iterativ zu ersetzen, um zu einer allgemeinen Form zu gelangen:

was zur allgemeinen Form führt:

Jetzt löse ich $n-2k = 1$ zum $k$Dies ist der Punkt, an dem die Wiederholung aufhört (wo $T(1)$) und geben Sie diesen Wert ein ($n/2 - 1/2 = k$) in die allgemeine Form:

Bei diesem letzten Schritt bin ich mir nicht sicher:

Ich würde das einfach als "argumentieren" $n \to \infty$ man kann ignorieren $-1/2$ und $n/2 \to n$? Ist diese Annahme richtig?

Beachten Sie, dass $3^{n/2-1/2} = \frac{1}{\sqrt{3}} 3^{n/2} = \frac 1{\sqrt{3}} \sqrt{3^n}$. Also die$-\frac 12$ in der Tat wird ein konstanter Faktor, der von der absorbiert wird $O()$, aber $\frac n2$ im Exponenten ändert sich die Basis und durch Ändern der Basis ändert sich die $O$-Klasse.

Die richtige Antwort lautet also $T(n) = O(3^{n/2}) = O(\sqrt{3^n})$.

Bis zum letzten Schritt war alles korrekt ... Sie fanden: