How to prove statement about $\mathcal{O}, \Theta$ and $\hbox{o}$?

Question

For a given function g,

Prove that $\hbox{o}(g) \neq O(g) - Θ(g)$.

Thanks for the help in advance

Answer 1

My comment apparently wasn't clear enough. The problem statement starts with let $f \in \mathcal{O}(g),~f \not\in \Theta(g)$ and $f \not\in \hbox{o}(g)$ so need to find $f$ or $g$ for this statement. We then quickly show that since $f \in \mathcal{O}(g),~f \not\in \Theta(g)$, we must have $f \in \mathcal{O}(g) - \Theta(g) = \{h\ |\ h \in \mathcal{O}(g) \mathrm{\ and\ } h \not\in \Theta(g)\}$. But we already know that $f \not\in \hbox{o}(g)$. Thus we have an element from the RHS which is not an element of the LHS so the two sides can not be equal as sets.

---

For two sets $A$ and $B$ to be equal, we must have that $A \subseteq B$ and $B \subseteq A$ where $\subseteq$ stands for subset. Formally, $A \subseteq B$ means that for any $x \in A$ we must have $x \in B$. So set equality basically says that pick anything from one set and we must be able to find it in the other set.

But in the problem above, we found a function $f$ that was part of one set but not part of the other set. Thus the two sets can not be equal.