Si $f(N)=\mathcal{O}\left(\frac{1}{\sqrt{N}}\right)$ (el gran-oh) significa que $\frac{1}{\sqrt{N}}$ crece más rápido que $f(N)$ como $N \to \infty$ . Así que es posible tomar $f(N)=\frac{1}{N}$ o $f(N)=\frac{1}{N^2}$ .
¿Estoy en lo cierto?
Cuando dices $f(N) = \mathcal{O} \left( g(N) \right)$ esto significa que $f(N)$ es igual a alguna función que tenga la propiedad
$$ f(N) \leq c g(N) $$
para todos $N \geq N_0$ y $c$ alguna constante. En su caso, esto significa que hay un $N_0$ y constante $c$ para lo cual
$$f(N) \leq \frac{c}{\sqrt{N}}.$$
Por lo tanto, sus opciones son ambas válidas como candidatas a $f(N)$ pero incluso trivialmente $f(N) = 0$ es un candidato adecuado.
Gracias. Ese es el problema. Podemos seleccionar muchas funciones válidas para $f(N)$ . Me he dado cuenta de que normalmente la gente toma directamente $M_{n}= \dfrac{1}{\sqrt{n}}$ ¿Es porque es el peor caso?
No sé cuál es su aplicación. Las cosas suelen funcionar de la siguiente manera, tienes algún tipo de recurrencia que quieres resolver, como la solución en forma cerrada es a veces complicada al menos "intentas adivinar" la clase de esa función. No es al revés (donde conoces la clase y eliges una función de esa clase). No estoy seguro de haber respondido a tu pregunta.
Por definición
$$f(x) = \mathcal{O}(g(x)) \iff f(x) \leq cg(x)$$
En su caso, deje que $f(N)=\dfrac{1}{N^a}$ con $a \in \mathbb{N} $ y $\,g(N)=\dfrac{1}{\sqrt{N}}$ entonces $$\lim_{N\to\infty}\frac{f(N)}{cg(N)} = \frac{\frac{1}{N^a}}{\frac{c}{\sqrt{N}}} = \frac{\sqrt{N}}{cN^a} = \sqrt{\frac{N}{(cN^a)^2}}= \frac{1}{cN^{\frac{a2-1}{2}}} =0 $$ Por lo tanto, $$f(N) \leq \dfrac{c}{\sqrt{N}}\implies f(N) = \mathcal{O}\left(g(N)\right) $$ $\tag*{$\Box$}$ Así que tienes razón.
Su "Nota" al final es errónea. Son no equivalente. Es cierto que $\lim f/g = c \geq 0 \implies f = O(g)$ pero lo contrario es falso.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
0 votos
No necesariamente crecer en absoluto (como se ve aquí), y en cualquier aspecto no estrictamente más rápido sino que limita desde arriba (hasta la multiplicación por la constante) todos los elementos excepto los finitos. Es decir, $\limsup\frac{f(N)}{1/\sqrt{N}}$ es finito. Efectivamente, las dos funciones que describes tienen esta propiedad.