está

Então, eu tenho esta pergunta para provar uma afirmação:

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

Eu não preciso saber como provar isso, apenas que, na minha opinião, isso não faz sentido e acho que deveria ser .$\Theta(n)\subset O(n)$

Meu entendimento é que é o conjunto de todas as funções que não fazem pior que n, enquanto Θ ( n ) é o conjunto de todas as funções que não fazem melhor e não é pior que n.$O(n)$$n$$\Theta(n)$

Usando isso, posso pensar no exemplo de uma função constante, digamos . Essa função certamente será um elemento de O ( n ), pois não será pior que n, pois n se aproxima de um número suficientemente grande.$g(n)=c$$O(n)$$n$$n$

No entanto, a mesma função não seria um elemento de Θ ( n ), pois g se sai melhor que n para grandes n ... Então, desde que g ∈ O ( n ) e g ∉ Θ ( n ) , então O ( n ) ∉ q ( n $g$$\Theta(n)$$n$$n$$g \in O(n)$$g \not\in \Theta(n)$$O(n)\not\in\Theta(n)$

Então a pergunta talvez esteja errada? Aprendi que é perigoso fazer essa suposição e, geralmente, perdi alguma coisa, simplesmente não consigo ver o que pode ser nesse caso.

Alguma ideia ? Muito obrigado..

Por sugestão de Rafael, transformei um comentário anterior nesta resposta.

Não é verdade que . De fato, , por definição. Portanto, temos .Θ ( f ( n ) ) = O ( f ( n ) ) ∩ ohms ( f ( n ) ) Θ ( f ( n ) ) ⊂ S ( f ( n ) $O(f(n)) \subset \Theta(f(n))$$\Theta(f(n)) = O(f(n)) \cap \Omega(f(n))$$\Theta(f(n)) \subset O(f(n))$

Pense dessa maneira: toda função que "não seja pior que n" e "não seja melhor que n" também é uma função que "não seja pior que n". A parte "não melhor que n" é apenas uma restrição adicional. Esta é uma aplicação direta da regra lógica que diz: . Por esse raciocínio, todas as funções que estão no conjunto também são membros do conjunto .Θ ( n ) O ( n $x \wedge y \implies x$$\Theta(n)$$O(n)$