Aproximación tilde para $\frac{N^{100}}{2^N}$ ?

Question

Estoy teniendo problemas para conseguir la aproximación de la tilde para una clase de algoritmos informáticos. Esto es lo que tengo hasta ahora:

$\frac{N^{100}}{2^N} \rightarrow \lg\left(\frac{N^{100}}{2^N}\right) = \lg(N^{100}) - \lg(2^N) = 100\lg(N) - N\lg(2)$

A partir de aquí estoy atascado. Estaba pensando que la tilde podría ser $0$ dado que $2^N$ crece más rápido de los dos.

Answer 1

No sé si he respondido a tu pregunta:

$f(N) = \frac{N^{100}}{2^N}$ no sólo está acotada, sino que finalmente llega a 0, ya que $N$ llega hasta el infinito. La respuesta corta es que para cualquier constante positiva $c$ y $k$ independiente de $N$ la función $e^{cN}$ siempre domina $N^k$ como $N$ se hace grande. Aunque, dependiendo de los valores específicos de $c$ y $K$ el valor de $N^k$ puede ser mucho mayor que $e^{cN}$ para valores "prácticos" de $N$ .

ETA: Parece que ya lo entiendes.

Así que $f(N) \in O(1)$ sería técnicamente correcto; $f(N) \in o(1)$ también sería correcto (y una afirmación más contundente ya que $o(1) \subset O(1)$ ). Realmente no estoy seguro de qué otra respuesta sería necesaria en este caso.

Sin embargo, lo que sería incorrecto es $f(N) \in \theta(1)$ eso implicaría que (dicho informalmente) $N^{100}$ y $2^N$ crecen de forma aproximadamente proporcional para $N$ arbitrariamente grande. Dicho de manera más formal, la afirmación $f(N) \in \theta(1)$ implicaría que existe un $\epsilon > 0$ tal que, para cualquier $N_0$ hay algo de $N > N_0$ tal que $|f(N)| > \epsilon$ . Y en este caso concreto no es cierto.

Answer 2

La proporción nunca supera $3.076*10^{172}$ en $N=144$ . Así que supongo que la aproximación sería una constante.