Problem Detail: So I have this question to prove a statement: $O(n)subsetTheta(n)$… I don’t need to know how to prove it, just that in my mind this makes no sense and I think it should rather be that $Theta(n)subset O(n)$. My understanding is that $O(n)$ is the set of all functions who do no worse than $n$ while $Theta(n)$ is the set of all functions that do no better and no worse than n. Using this, I can think of the example of a constant function say $g(n)=c$. This function will surely be an element of $O(n)$ as it will do no worse than $n$ as $n$ approaches a sufficiently large number. However, the same function $g$ would not be an element of $Theta(n)$ as g does do better than $n$ for large $n$… Then since $g in O(n)$ and $g notin Theta(n)$, then $O(n)notinTheta(n)$ So is the question perhaps wrong ? I’ve learnt it is dangerous to make that assumption and usually I have missed something, I just can’t see what it might be in this case. Any thoughts ? Thanks a lot..
Asked By : Ronald
Answered By : Patrick87
At the suggestion of Raphael, I have turned a previous comment into this answer. It is not true that $O(f(n)) subset Theta(f(n))$. In fact, $Theta(f(n)) = O(f(n)) cap Omega(f(n))$, by definition. So we have $Theta(f(n)) subset O(f(n))$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/3240 Ask a Question Download Related Notes/Documents
