Yo estaba tratando de acotar el costo máximo de arriba hacia abajo merge sort: $$ f(0) = f(1) = 0,\quad f(n) = n\lceil{\lg n}\rceil - 2^{\lceil\lg n\rceil} + 1, $$ donde $\lg n$ es el logaritmo binario de $n$ $\lceil{x}\rceil$ es el entero más pequeño mayor o igual a $x$. Deje $\{x\}$ la parte fraccionaria de $x$. He hecho dos casos:
- Si $n=2^p$,$f(n) = n\lg n - n + 1$;
- otra cosa $\lceil\lg n\rceil = \lg n -\{\lg n\}+1$$f(n) = n\lg n + \theta(1-\{\lg n\}) \cdot n + 1$,$\theta(x) := x - 2^x$. La derivada de $\theta$ muestra que $\max_{0<x\leqslant 1}\theta(x) = -(1+\ln\ln{2})/\!\ln{2} \simeq -0.9139$ y $\min_{0<x\leqslant 1}\theta(x) = \theta(1) = -1$.
Así que tenemos $n\lg n - n + 1 \leqslant f(n) < n\lg n - 0.91 n + 1.$ Considerando $\theta(1-\{\lg n\})$, el límite inferior es apretado si $\{\lg n\} = 0$ o, de manera equivalente, $n=2^p$.
Lo que quiero es caracterizar la $n$ que $f(n)$ es el más cercano al límite superior: $\theta'(x) = 0 \Leftrightarrow x = -\lg\ln 2$, lo $\theta'(1-\{\lg n\}) = 0 \Leftrightarrow \{\lg n\} = 1 + \lg\ln 2$.
¿Cómo puedo caracterizar los números naturales $n$ tal que $\{\lg n\}$ es como cerca como sea posible a $1 + \lg\ln 2$? Por ejemplo, podría ser $n=2^p-1$? $2^p+1$?
EDITAR En los comentarios, la solución real es de $2^k\ln 2$, lo que plantea la cuestión del entero de solución. Suponiendo que el entero más cercano es la solución, el primero de los valores de $k=1$ $12$$2$, $3$, $6$, $11$, $22$, $44$, $89$, $177$, $355$, $710$, $1420$, $2839$. Es la suposición de derecho? ¿Cuál es el término general?
