¿ está contenido en ?

Entonces tengo esta pregunta para probar una declaración:

$O(n)\subset\Theta(n)$ ...

No necesito saber cómo demostrarlo, solo que en mi opinión esto no tiene sentido y creo que debería ser ese .$\Theta(n)\subset O(n)$

Tengo entendido que es el conjunto de todas las funciones que no funcionan peor que mientras que es el conjunto de todas las funciones que no funcionan mejor ni peor que n.$O(n)$$n$$\Theta(n)$

Usando esto, puedo pensar en el ejemplo de una función constante, digamos . Esta función seguramente será un elemento de ya que no será peor que cuando acerque a un número suficientemente grande.$g(n)=c$$O(n)$$n$$n$

Sin embargo, la misma función no sería un elemento de ya que g funciona mejor que para grande ... Entonces, dado que y , entonces$g$$\Theta(n)$$n$$n$$g \in O(n)$$g \not\in \Theta(n)$$O(n)\not\in\Theta(n)$

Entonces, ¿la pregunta tal vez sea incorrecta? Aprendí que es peligroso hacer esa suposición y, por lo general, me he perdido algo, simplemente no puedo ver qué podría ser en este caso.

Alguna idea ? Muchas gracias..

Por sugerencia de Raphael, he convertido un comentario anterior en esta respuesta.

No es cierto que . De hecho, , por definición. Entonces tenemos .$O(f(n)) \subset \Theta(f(n))$$\Theta(f(n)) = O(f(n)) \cap \Omega(f(n))$$\Theta(f(n)) \subset O(f(n))$

Piénselo de esta manera: cada función que hace "no peor que n" y "no mejor que n" es también una función que hace "no peor que n". La parte "no mejor que n" es solo una restricción adicional. Esta es una aplicación directa de la regla lógica que dice: . Según este razonamiento, todas las funciones que están en el conjunto también son miembros del conjunto .$x \wedge y \implies x$$\Theta(n)$$O(n)$