Cómo calcular la notación Big-oh de una función

Answer 1

Permítanme comenzar escribiendo la definición real:

Decimos [matemática] f (x) \ = \ O (g (x)) [/ matemática] si hay números positivos [matemática] M, \ x_0 [/ matemática] tal que para cualquier [matemática] x \ geq x_0 [/ math] tenemos [math] f (x) \ leq Mg (x) [/ math]. Tenga en cuenta que si [matemáticas] f (x), g (x)> 0 [/ matemáticas], esto es equivalente a decir que desde algún punto, [matemáticas] \ frac {f (x)} {g (x)} [/ math] está acotado.

Lo primero que hay que tener en cuenta aquí es preguntar “¿Cómo calculamos [matemáticas] O (f (x)) [/ matemáticas]?” Realmente no tiene ningún significado. Para la mayoría de las opciones de [math] f [/ math], hay muchas funciones [math] g [/ math] con [math] g (x) = O (f (x)) [/ math]. Con eso en mente, analicemos uno de sus ejemplos.

1. Usaremos la segunda versión de la definición que di aquí. Tenemos

[matemáticas]
\ frac {(2 ^ {\ log (n)}) ^ {\ log (n)}} {n ^ {n \ log (n)}}

= \ frac {n ^ {\ log (2) \ log (n)}} {n ^ {n \ log (n)}}

= n ^ {\ log (n) (2-n)}
[/matemáticas]

Lo que de hecho tiende a 0 para grandes [matemáticas] n [/ matemáticas], por lo que está acotado, por lo que su primer ejemplo es verdadero.

2. Estas dos funciones son iguales, y claramente siempre tenemos [matemáticas] f (x) = O (f (x)) [/ matemáticas], por lo que esta también es cierta.

Tal vez esto sea suficiente para que pueda resolver el tercer ejemplo por su cuenta.

Answer 2

Si para valores suficientemente grandes de n, la función debajo de O grande siempre producirá números mayores o iguales que la función base.

Entonces, simplemente tiene que demostrar que este comportamiento es verdadero después de cierto valor para esas funciones.