¿[Math] \ Theta (n ^ 2) [/ math] incluye [math] O (n ^ 3) [/ math]?

Answer 1

Para que una función [matemática] f (n) [/ matemática] esté contenida en [matemática] \ Theta (n ^ 2) [/ matemática], debe ajustarse al criterio [matemática] \ existe k_1, \ existe k_2, \ existe n_0, \ forall n> n_0 ~ k_1 n ^ 2 \ leq f (n) \ leq k_2 n ^ 2 [/ math]. Esto en parte significa que [math] f (n) [/ math] está delimitado a continuación por [math] n ^ 2 [/ math], y aquí radica nuestro problema. Ahora, para que una función [matemática] f (n) [/ matemática] esté contenida en [matemática] O (n ^ 3) [/ matemática], es necesario que [matemática] \ exista k, \ exista n_0 \ forall n> n_0 ~ f (n) \ leq kn ^ 3 [/ matemática]. Podemos mostrar que hay funciones dentro de [matemáticas] O (n ^ 3) [/ matemáticas] y no dentro de [matemáticas] \ Theta (n ^ 2) [/ matemáticas] al mostrar que su diferencia establecida, es decir, [matemáticas] \ {f (n) ~ | ~ f (n) \ in \ mathbb {R} \ rightarrow \ mathbb {R}, ~ \ exist k, \ exist k_1, \ exist k_2, \ exist n_0, \ exist n_0 ‘\ left (\ forall n> n_0 ~ f (n) \ leq kn ^ 3 \ right) \ wedge \ left (\ forall n> n_0 ‘~ k_1 n ^ 2 \ leq f (n) \ leq k_2 n ^ 2 \ right) [/ math] [math] \} [/ math], no está vacío. Y de hecho, hay funciones que no están delimitadas a continuación por [math] n ^ 2 [/ math] y están limitadas por [math] n ^ 3 [/ math]. Un ejemplo: [matemáticas] f (n) = n [/ matemáticas]. Podemos verificar que [math] \ exist k, \ exist n_0 \ forall n> n_0 ~ n \ leq kn ^ 3 [/ math] se mantiene, y que, al mismo tiempo, [math] \ exist k_1, \ exist k_2 , \ exist n_0 \ forall n> n_0 ~ k_1 n ^ 2 \ leq n \ leq k_2 n ^ 2 [/ math] no.

Intuitivamente hablando, [matemática] \ Theta (n ^ 2) [/ matemática] no incluye [matemática] O (n ^ 3) [/ matemática] porque hay funciones limitadas anteriormente por [matemática] n ^ 3 [/ matemática] que no están delimitados a continuación por [math] n ^ 2 [/ math], y [math] n [/ math] es un ejemplo de dicha función.

Answer 2

No, porque [matemáticas] f (n) = n \ en O (n ^ 3) [/ matemáticas] y [matemáticas] f (n) = n ^ 3 \ en O (n ^ 3) [/ matemáticas] pero tampoco están en [matemáticas] \ Theta (n ^ 2) [/ matemáticas]. [math] \ Theta (n ^ 2) [/ math] solo incluye funciones que están asintóticamente limitadas tanto arriba como abajo por múltiplos constantes de [math] n ^ 2 [/ math]. Como todas las funciones delimitadas anteriormente por [math] n ^ 2 [/ math] también están delimitadas por [math] n ^ 3 [/ math], lo contrario es cierto. [matemáticas] O (n ^ 3) [/ matemáticas] es un superconjunto de (incluye) [matemáticas] \ Theta (n ^ 2) [/ matemáticas].

Answer 3

No, al revés: [matemáticas] O (n ^ 3) [/ matemáticas] incluye [matemáticas] \ Theta (n ^ 2) [/ matemáticas]. La gran [math] O [/ math] es un límite superior, lo que significa que es el conjunto de todas las funciones que crecen no más rápido que proporcionalmente a [math] n [/ math] al cubo. Los límites [math] \ Theta [/ math] desde arriba y abajo, por lo tanto, solo contienen funciones que crecen proporcionalmente a [math] n [/ math] al cuadrado. Por lo tanto, todas las funciones en [matemáticas] \ Theta (n ^ 2) [/ matemáticas] también están en [matemáticas] O (n ^ 3) [/ matemáticas].