¿Cuál es el límite de: $ T(n)=T(n-2)+\log(n)$?

Question

Da: $T(n)=T(n-2)+\log(n)$

Necesito encontrar el límite para la repetición anterior.

Entonces: $$\begin{align} T(n-2)&=T(n-2-2)+\log(n-2)\ &=T(n-4)+\log(n-2)\ T(n)&=T(n-2)+\log(n)\ &=T(n-4)+\log(n-2)+\log(n)\ T(n-4)&=T((n-4)-2)+\log(n-4)\ T(n)&=T(n-4)+\log(n-2)+\log(n)\ &=T(n-6)+\log(n-4)+\log(n-2)+\log(n)\ &\vdots\ T(n)&=\Theta(2)+\sum{i=1}^n\log(2i)\ &=\Theta(2)+\log\left(\Pi{i=1}^n2i\right)\ &=\Theta(2)+\log((2i)!)\ &=\Theta(n\log(n)) \end{align} $ es esto correcto?

Saludos

Answer 1

Has cometido un par de errores: has supone implícitamente que $n$ es aún, y has miscounted los pasos necesarios para reducir el $T(n)$.

Si $n=2m$, su cálculo, con los errores corregidos, muestra que $$T(n)=T(0)+\sum_{k=1}^m\log 2k\;;$$ if $n=2m+1$, it shows that $$T(n)=T(1)+\sum_{k=1}^m\log(2k+1)\;.$$

En cada caso la suma ha $\lfloor n/2\rfloor$ términos, cada uno de los cuales es en la mayoría de las $\log n$, por lo que $$T(n)\le\max\{T(0),T(1)\}+\frac{n}2\log n\;;$$ this clearly implies that $T(n)$ is $O(n\log n)$.

Si quieres mirar más de cerca, se puede calcular que $$\sum_{k=1}^n\log 2k=\log\prod_{k=1}^m 2k=\log 2^mm!\;,$$ y

$$\begin{align*} \sum_{k=1}^m\log(2k+1)&=\log\prod_{k=1}^m(2k+1)\\ &=\log\Big(3\cdot5\cdot \ldots\cdot(2m+1)\Big)\\ &=\log\frac{(2m+1)!}{2\cdot4\cdot\ldots\cdot(2m)}\\ &=\log\frac{(2m+1)!}{2^mm!}\;, \end{align*}$$

pero estos no son fácilmente va a dar buen límites mejor que la que ya tienen. Una mejor idea, si usted necesita información más precisa, se nota que las sumas de los registros puede ser aproximada por integrales sobre los límites apropiados de la función $f(x)=\log 2x$.

Answer 2

La suma de $\log(n) + \log(n-2) + \dots $ tiene más de $n/2$ términos con cada plazo $\leq \log(n)$. Esto conduce a una cota superior de a $(n/2)\log(n)$. Para entender más precisa asymptotics de $T(n)$ la suma de los logaritmos se pueden comparar geométricamente y algebraicamente a $\int_0^{(n-1)/2} \log (n-2x) dx$.

La derivación en la pregunta es correcta incluso para $n$, con un argumento similar válido para la extraño $n$, suponiendo que el $\log n! = O(n \log n)$ es conocido. Usando la aproximación de Stirling, muy estimaciones precisas de $T(2k)$ $T(2k+1)$ puede ser que vaya más allá del paso a la función o trapezoidal aproximaciones a la integral.

Answer 3

Creo que porque tenemos $\frac n2$ condiciones, por lo que la respuesta sería $\frac n2 \cdot \log(n)$ y así sucesivamente la respuesta sería $O(n\log(n))$.