[Solved]: "Not in big theta but in big O"

Problem Detail: 

Can somebody please help me understand ways I can attempt to find two functions f(x) and g(x) in which f(x) is in big O of g(x) but not big theta of g(x). I get that this is asking me to prove that f(x) isn't in big omega of g(x) but I really don't know where to start with this one. I tried to look for scenerios where there wouldn't be any positive constants. However, I had trouble doing that.

Asked By : tiredasalways

Answered By : Shreesh

One of the answers to your question: $f(n) = n$, and $g(n) = n^2$.

Then $f(n) = O(g(n))$ but not $\Theta(g(n))$. This is because $n^2$ is an upper bound on $n$ , for all $n \geq 0$, but it is not tight (actually we only need the inequality to be true for $n > N$ for some $N$, by the definition of $O()$).

By saying that the bound is not tight, what we mean is that we do not have $cn^2 \leq n \leq c'n^2$, for large enough $n$'s (it should hold for all $n > N'$ for some $N'$ by the definition of $\Theta()$ if $n$ were $\Theta(n^2)$). Also $c$ and $c'$ are positive here and the following discussion.

Since $n^2$ is upper bound on $n$ it is easy to get $n \leq c'n^2$ part. But we can never get to the $cn^2 \leq n$ part. Even if we take $c$ very small,say 0.01 in the picture, at $n > 100$ it will not remain smaller. So we can never have $n$ between $cn^2$ and $c'n^2$ for all values $n>N'$. This is because we will always find some big number where $c'n^2$ will be above $n$.

$O()$ is just an upper bound, where as $\Theta()$ is a tight bound. Also if we have $f(n) = o(g(n))$ then the bound in not tight yet it is an upper bound. Then $g(n)$ is a loose upper bound. If $f(n) = o(g(n))$ then any such pair of $f(n)$ and $g(n)$ will satisfy the condition of your question.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53419