Decidir si una función es O(n), Ω(n) o Θ(n).

Question

En primer lugar, esta es mi pregunta de tarea, tengo mis respuestas y quiero estar seguro de si me estoy perdiendo algo. Tengo dificultades para decidir si f(n) es O(g(n)), (g(n)), o (g(n)):

a) f(n)= n 0,1234 g(n)= n 0,1233 . Creo que aquí f(n) es (g(n)) ya que g(n)

b) f(n)= 4 n g(n)= 5 n . Creo que aquí f(n) = O(g(n)) ya que 5 n siempre domina

c) f(n)=n + log(log 2 n), g(n)=100n + (log(n)) 2 . Aquí creo que f(n) es (g(n)) porque normalmente, g(n) domina pero 10000f(n) domina a g(n), por ejemplo.

d) f(n)=3n(log(n!)) + n 2 g(n)=n 2 log(log(n)). Me parece que f(n) es O(g(n)) ya que g(n) siempre domina a

e)f(n)= f(n)+O(f(n)), g(n)= (f(n)). Aquí creo que f(n) es (g(n)).

¿Tengo razón en mis respuestas? Gracias por su ayuda.

Answer 1

Tomemos como ejemplo d): $ \log n! =\sum_{k=1}^{n} \log k \approx \int_{1}^{n} \log x dx = n \log n$ . Por lo tanto $f(n) = 3 n^2 \log n + n^2 < 3 n^2 \log n +3 n^2 = 3n^2 ( \log n +1) \leq 6 n^2 \log n = O(n^2 \log n)$ . Por lo tanto $f(n)=O(n^2 \log n)$ . Ahora toma el límite $\lim_{n \to \infty} \frac{f(n)}{g(n)}$ que tiende claramente a infinito. Por lo tanto $f(n) = \omega((f(n))$ .