Cómo es$O(\log(\log(n)))$$O( \log n)$?
He visto este resultado en algún lugar de esto, pero yo todavía no entiendo muy bien cómo esto es cierto. Esto también me ayudan a calcular los Grandes de Omega de la misma función.
Cómo es$O(\log(\log(n)))$$O( \log n)$?
He visto este resultado en algún lugar de esto, pero yo todavía no entiendo muy bien cómo esto es cierto. Esto también me ayudan a calcular los Grandes de Omega de la misma función.
Supongamos $f(n) = O(\log\log n)$, y queremos demostrar que $f(n) = O(\log n)$.
Suponga $f(n)$ es una función positiva. Por la definición de la gran $O$ notación, $f(n) = O(\log\log n)$ implica que existe un $N_0$ y una constante positiva $k$ tal que $$ f(n) \leq k\cdot \log\log n, \ \forall n \geq N_0 $$
Desde $\log\log n \leq \log n$ para suficientemente grande $n$, debe existir una $N_1$ tal que $$ f(n) \leq k \cdot \log n, \ \forall n \geq N_1 $$ por lo tanto $f(n) = O(\log n)$.
En primer lugar, asumimos que todas las funciones son no negativos. $f(n)$ $O(g(n))$ si $$\lim_{n\rightarrow \infty} \sup \frac{f(n)}{g(n)} \leq K<\infty\quad(1)$$ where the finite constant $K$ is independent of $n.$ Thus if $f(n)=O(g(n))$ and $h(n)\leq f(n)$ for $n$ large enough, then $h(n)=O(g(n)).$
Si $K=0$, entonces decimos que $f(n)=o(g(n))$, pero todavía mantiene ese $f(n)=O(g(n)).$
Si $f(n)=O(g(n))$ $g(n)=O(f(n))$ $f(n)=\Theta(g(n))$ es decir, son el mismo orden hasta finita y constante, para $n$ lo suficientemente grande.
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.