Resolvendo a recorrência T (n) = 3T (n-2) com o método iterativo

Já faz um tempo desde que tive que resolver uma recorrência e queria ter certeza de que entendia o método iterativo de resolver esses problemas. Dado:

$$T(n) = 3T(n-2)$$

Meu primeiro passo foi substituir termos iterativamente para chegar a uma forma geral:

$$T(n-2) = 3T(n-2 -2) = 3T(n-4)$$ $$T(n) = 3 *3T(n-4)$$

levando à forma geral:

$$T(n) = 3^k T(n-2k)$$

Agora, resolvo $n-2k = 1$ para $k$ , que é o ponto em que a recorrência para (onde $T(1)$ ) e insiro esse valor ( $n/2 - 1/2 = k$ ) na forma geral:

$$T(n) = 3^{n/2-1/2}$$ $$T(n) = O(3^n)$$

Não tenho certeza sobre o último passo:

Gostaria apenas de "argumentar" que, como se pode ignorar e ? Essa suposição está correta?$n \to \infty$$-1/2$$n/2 \to n$

Observe que . Portanto, o se torna um fator constante absorvido pelo , mas no expoente altera a base e a alteração da base altera a classe$3^{n/2-1/2} = \frac{1}{\sqrt{3}} 3^{n/2} = \frac 1{\sqrt{3}} \sqrt{3^n}$$-\frac 12$$O()$$\frac n2$$O$

A resposta correta é .$T(n) = O(3^{n/2}) = O(\sqrt{3^n})$

Tudo estava correto até o último passo ... você encontrou:

$$T(n) \propto 3^{\frac{n}{2}- \frac{1}{2}} = \left(3^{n - 1}\right)^{\frac{1}{2}} = \frac{1}{\sqrt{3}}\left(\sqrt{3}\right)^n$$