[Solved]: “Not in big theta but in big O”

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.