Cómo solucionar $n < 2^{n/8}$$n$?

Question

Esto es de un ejercicio (1.2.2) en la introducción a los algoritmos que estoy trabajando en la privada.

Para encontrar en qué punto un $n \lg n$ función se ejecutará más rápido que un $n^2$ función de lo que necesito averiguar para qué valor de $n$

$8n^2 > 64n \lg n$

(con lg aquí está el log binario) después de algunos primaria simplificación tenemos

$n > 8\lg n$

Jugando con las propiedades de registro puedo más que esto

$n^8 < 2^n$

o

$n < 2^{n/8}$

Aunque estoy seguro de que es algo muy elemental que me he perdido en algún lugar a lo largo de los años, después de ver un par de logaritmo tutoriales yo no soy así encontrar la manera de obtener ninguna más en esto.

Cualquier ayuda con la solución de $n$ sería apreciada.

Answer 1

Ya que no toma mucho tiempo para $2^{n/8}$ a ser más grande que el de $n$, sería razonable que experimentar para encontrar más o menos donde esto sucede, utilizando múltiplos de $8$ sea fácil. E. g., $40\gt 2^5$, pero $48<2^6$. El más pequeño de la solución (no recuento $n=1$) por lo tanto está en algún lugar entre el$41$$48$. Es geométricamente clara de la forma de las curvas de $y=x$ $y=2^{x/8}$ que todos mayor $n$ va a funcionar, pero para demostrar que usted podría utilizar la inducción matemática.

Reclamo: Si $n\geq 44$,$n\lt 2^{n/8}$.

Prueba: El caso base es $n=44$, para que voy a omitir la verificación. Supongamos que para algunos $n\geq 44$ que $n\lt 2^{n/8}$. A continuación,$2^{(n+1)/8}=2^{1/8}2^{n/8}\gt 2^{1/8}n$. Desde $n\geq 44$, $\frac{n+1}{n}=1+\frac{1}{n}\leq 1+\frac{1}{44}\lt 2^{1/8}$. Por lo tanto $2^{1/8}n\gt n+1$, y la combinación con la anterior desigualdad completa el paso inductivo.

Yo también voy a omitir la comprobación de que se $43\gt 2^{43/8}$.

Answer 2

No es difícil mostrar que $f(x) = x - 8 \lg x$ sólo tiene un punto crítico. Desde $f(2) \lt 0$ es suficiente para encontrar $x \gt 2$ tal que $f(x) > 0$.

Tome $n = 2^{k}$, entonces usted consigue $2^{k} > 8k$ a partir de su segundo de la desigualdad y de conectar $k$ $1$ sobre la muestra que $n = 2^6 = 64$ va a hacer. Usted puede comprobar con la mano que $n = 44$ es óptimo, como $f(44) \gt 0 \gt f(43)$.

Answer 3

Los Lambert $W$ función se puede utilizar para resolver ecuaciones de la forma $p^{ax+b} = cx+d.$ De hecho, la página de la Wikipedia da la solución a $n = 2^{n/8}$

$$n = \frac{-8}{\ln 2} W\left(\frac{-\ln 2}{8}\right).$$

Via Mathematica, which implements the $W$ function as ProductLog, this comes out to be 43.5592 (although you have to take the lower branch of the $P$ (función), de acuerdo con el método de Newton iteración solución Theo Buehler menciona.