Usando límites para determinar Big-O, Big-Omega y Big-Theta

Question

Estoy tratando de obtener una respuesta concreta sobre el uso de límites para determinar si dos funciones, $f(n)$ y $g(n)$, son de orden Big-$O$, Big-$\Omega$ o Big-$\Theta$. He revisado mi libro, mis apuntes de clase e incluso he hecho algunas investigaciones en línea, pero aún no he encontrado nada que me dé una respuesta sólida. Según mi entendimiento sobre cada una de las tres notaciones, he elaborado 3 conjuntos de reglas:

$\displaystyle f(n) = O(g(n)) \implies \lim_{n \to \infty}\;\frac{f(n)}{g(n)} = 0$

$\displaystyle f(n) = \Omega(g(n)) \implies \lim_{n \to \infty}\;\frac{f(n)}{g(n)} = \infty$

$\displaystyle f(n) = \Theta(g(n)) \implies 0 < \; \lim_{n \to \infty} \; \frac{f(n)}{g(n)} \;< \infty$

La razón por la que estoy tratando de obtener una respuesta tan definitiva sobre esto es porque para una tarea tenemos que explicar brevemente por qué $\;f(n) = O(g(n))$, $\;f(n) = \Omega(g(n)),$ o $\;f(n) = \Theta(g(n))$. Si puedo simplemente usar esas 3 reglas anteriores, mis explicaciones serán cortas, concisas y al punto.

Cualquier ayuda o consejo sería muy apreciado

Answer 1

La notación grande / pequeña O / Ω / Θ no está definida o, de hecho, no es adecuadamente definible en términos de límites. En particular, es posible, por ejemplo, que $f(n) = \Theta(g(n))$ aunque $f(n) \mathbin/ g(n)$ no converge a un límite.

(Para un contraejemplo simple, elige cualquier función $g(n) > 0$ y deja que $f(n) = (2 + (-1)^n)\, g(n)$. En otras palabras, $f(n) = g(n)$ para $n$ impar y $f(n) = 3g(n)$ para $n$ par.)

Dicho esto, cuando la razón $f(n) \mathbin/ g(n)$ converge (o tiende a infinito), podemos determinar la relación asintótica entre $f(n)$ y $g(n)$ a partir del valor del límite. En particular, como se señala en la útil Hoja de trucos sobre asintóticas por Tom Leighton y Ronitt Rubinfeld, como enlazado por bigworld12 en los comentarios anteriores,

Las definiciones de las diversas notaciones asintóticas están estrechamente relacionadas con la definición de un límite. Como resultado, $\lim_{n→∞} f(n) \mathbin/ g(n)$ revela mucho sobre la relación asintótica entre $f$ y $g$, siempre y cuando exista el límite. La siguiente tabla traduce hechos sobre el límite de $f \mathbin/ g$ en hechos sobre la relación asintótica entre $f$ y $g$. $$\begin{array}{lllllll} \lim_{n→∞} f(n)\mathbin/g(n) \ne 0,∞ &\implies& f = Θ(g) && \lim_{n→∞} f(n)\mathbin/g(n) = 1 &\implies& f ∼ g \\ \lim_{n→∞} f(n)\mathbin/g(n) \ne ∞ &\implies& f = O(g) && \lim_{n→∞} f(n)\mathbin/g(n) = 0 &\implies& f = o(g) \\ \lim_{n→∞} f(n)\mathbin/g(n) \ne 0 &\implies& f = Ω(g) && \lim_{n→∞} f(n)\mathbin/g(n) = ∞ &\implies& f = ω(g) \\ \end{array}$$

Answer 2

La respuesta de Ilmari es aproximadamente correcta, pero quiero decir que los límites son en realidad la forma incorrecta de pensar sobre la notación asintótica y las expansiones, no solo porque no siempre se pueden usar (como Did e Ilmari ya señalaron), sino también porque no logran capturar la verdadera naturaleza del comportamiento asintótico incluso cuando se pueden usar.

Hay que tener en cuenta que para ser preciso, uno siempre tiene que especificar exactamente cuáles variables de límite se están considerando en relación con el comportamiento asintótico. En informática, suele ser a medida que algunos parámetros de tamaño tienden a infinito. En matemáticas, a menudo es a medida que algún parámetro de umbral tiende a cero, o a medida que algún punto tiende a otro punto.

$f(n)∈O(g(n))$ cuando $n→∞$ si para algún $c∈\mathbb{R}$ tenemos que $|f(n)| ≤ c·|g(n)|$ cuando $n→∞$.

$f(n)∈Ω(g(n))$ cuando $n→∞$ si para algún $c∈\mathbb{R}_{>0}$ tenemos que $|f(n)| ≥ c·|g(n)|$ cuando $n→∞$.

$f(n)∈o(g(n))$ cuando $n→∞$ si para cada $c∈\mathbb{R}_{>0}$ tenemos que $|f(n)| ≤ c·|g(n)|$ cuando $n→∞$.

$f(n)∈ω(g(n))$ cuando $n→∞$ si para cada $c∈\mathbb{R}$ tenemos que $|f(n)| ≥ c·|g(n)|$ cuando $n→∞$.

$f(n)∈Θ(g(n))$ cuando $n→∞$ si tanto $f(n)∈O(g(n))$ como $f(n)∈Ω(g(n))$ cuando $n→∞$.

Para ser completamente preciso, también se debe especificar el tipo de variable de límite ($n$ en este caso), aunque generalmente se omite si es claro en el contexto (y "$n$" se reserva generalmente para enteros).

Lo mismo ocurre con las afirmaciones del comportamiento asintótico "a medida que $x→0$" en lugar de "a medida que $n→∞$". Hay que tener en cuenta que estas definiciones funcionan incluso cuando $f,g$ son valores complejos.

Para hacer claras las definiciones anteriores, una afirmación de la forma "$A(n)≤B(n)$ a medida que $n→∞$" con $n∈\mathbb{N}$ significa "para algún $m∈\mathbb{N}$ tenemos ( $A(n)≤B(n)$ para cada $n∈\mathbb{N}_{>m}$ )".

Por ejemplo, $3n^2+4n ∈ O(n^2)$ a medida que $n→∞$ porque $|3n^2+4n| ≤ 7·|n^2|$ para cada $n∈\mathbb{N}_{>1}$. Y así es como se debe pensar en el comportamiento asintótico; simplemente oculta una constante (en este caso $7$) en la desigualdad entre los valores absolutos.

Finalmente, muchos resultados asintóticos útiles se mantienen incluso cuando el límite no existe, y es mucho más fácil usar la definición original incluso si el límite existe. Por ejemplo, el ordenamiento de burbuja siempre realiza $O(n^2)$ comparaciones, porque hay a lo sumo $n$ iteraciones del bucle externo, cada uno de los cuales ejecuta el bucle interno durante a lo sumo $n$ iteraciones. En una lista ordenada, el ordenamiento de burbuja solo realiza $O(n)$ comparaciones, por lo que el límite no se cumple. Incluso si se analiza el peor de los casos, es más difícil (y ridículo) calcular el límite de la razón del número de comparaciones del peor de los casos sobre $n^2$...

De manera similar, muchos algoritmos numéricos como la aproximación de Newton-Raphson garantizan cierto comportamiento de convergencia del algoritmo, pero de ninguna manera garantizan ningún tipo de límite. ¡Después de todo, el algoritmo puede converger más rápido de lo garantizado!

Answer 3

Su primera ecuación es incorrecta para Big-O. No es para Big-O, es para little-o (o).

Se define little-o como, f(n) y g(n) son dos funciones reales dadas, g(n) es distinta de cero o se hace distinta de cero después de cierto punto, entonces,

\begin{align} \lim_{n \to \infty}\frac{f(n)}{g(n)} = 0 \Longrightarrow f(n) = o(g(n)) \end{align}

A continuación se muestra la definición de límite de Big-$O$, Big-$\Omega$ y Big-$\Theta$.

Big-$O$ :

Sean f(n) y g(n) dos funciones reales, entonces, $f(n)=O(g(n))$ es equivalente a

\begin{align} \exists~ c\in\mathbb{R}: \lim_{n \to \infty}\frac{f(n)}{g(n)} = c \end{align}

donde, $c \geqslant 0 $

(Aquí $c$ es finito o puede ser cero)

Entonces, si se prueba que el límite anterior es igual a $0$ entonces se puede decir que $f(n)=O(g(n))$. Sin embargo, si no es igual a $0$ y $c > 0$, entonces no se puede afirmar con certeza que $f(n)$ no pertenece a $O(g(n))$

Big-$\Omega$ :

Sean f(n) y g(n) dos funciones reales, entonces, $f(n)=\Omega(g(n))$ es equivalente a

\begin{align} \lim_{n \to \infty}\frac{f(n)}{g(n)} = c \end{align}

donde $0 < c \leqslant \infty$

(Aquí $c$ es mayor que cero O puede ser infinito-$\infty$)

Si se demuestra que el límite anterior es igual a $\infty$ entonces es suficiente escribir $f(n)=\Omega(g(n))$

Big-$\Theta$ :

Sean f(n) y g(n) dos funciones reales, entonces f(n) = $\Theta$(g(n)) es equivalente a

\begin{align} \lim_{n \to \infty}\frac{f(n)}{g(n)} = c, donde ~0 < c < \infty \end{align}

Si se prueba que el límite anterior es mayor que $0$ y no es $\infty$ entonces es suficiente decir $f(n)=\Theta(g(n))$

---

Veamos un ejemplo para aclarar aún más.

El siguiente ejemplo se toma del Manual de Diseño de Algoritmos 2da Edición.

TADM2E-2.8(a)

$f(n) = \log n^2$; $g(n) = \log n + 5$

Solución-1

\begin{align} \lim_{n \to \infty}\frac{\log n^2}{\log n + 5} \end{align>

Aplicando la Regla de L'Hopital

\begin{align} \lim_{n \to \infty}\frac{\log n^2}{\log n + 5} = \lim_{n \to \infty}\frac{\frac{2}{n\ln 10}}{\frac{1}{n\ln 10}} = \lim_{n \to \infty}(2) = 2 \end{align>

Entonces,

\begin{align} 0 < \lim_{n \to \infty}\frac{\log n^2}{\log n + 5} = 2 < \infty \end{align>

Por eso podemos escribir $f(n)=\Theta(g(n))$

Solución-2

También se puede resolver el ejemplo anterior volviendo a la definición formal de $Big-\Theta$ como se describe en el libro TADM.

• $f(n) = \Theta(g(n))$ significa que $c_1.g(n)$ es una cota superior para $f(n)$ y $c_2.g(n)$ es una cota inferior para $f(n)$, para todo $n>n_0$. Por lo tanto, existen constantes $c_1$ y $c_2$ tales que $f(n) \le c1.g(n)$ y $f(n) \ge c2.g(n)$. Esto significa que g(n) proporciona una cota ajustada y agradable para f(n).

Entonces, para resolver el problema anterior necesitamos encontrar $c_1$ y $c_2$, de manera que $f(n) \le c_1.g(n)$ y $f(n) \ge c_2.g(n)$. Necesitamos demostrar que $f(n) = O(g(n))$ y $f(n) = \Omega(g(n)).

$$\log n^2 = 2.\log n $$ $$2.\log n \le 2.\log n + 10$$ $$\log n^2 \le 2(\log n + 5)$$ $$\log n^2 \le c_1(\log n + 5) (donde ~c_1 = 2)$$ $$\log n^2 = O(\log n + 5) $$

Y,

$$\log n + 5 \le \log n + 5 \log n$$ $$\log n + 5 \le 6 \log n$$ $$\log n + 5 \le 3.2 \log n $$ $$3.\log n^2 \ge \log n + 5$$ $$\log n^2 \ge c_2(\log n + 5) (donde~ c_2 = \frac{1}{3})$$ $$\log n^2 = \Omega(\log n + 5)$$

Así,

$$\log n^2 = \Theta(\log n + 5)$$

NOTA :

En Solución-1, $c$ cumple todas las condiciones para $Big-O$, $Big-\Omega$ y $Big-\Theta$

Por lo tanto, $f(n)=O(g(n))$ y $f(n)=\Omega(g(n)) por eso es $f(n)=\Theta(g(n))$. Esto confirma la definición formal mencionada anteriormente.

---

Lee más

Aquí está la tabla que muestra la idea general

También lee la diferencia entre Big-$O$ y little-$o$