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.
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Just FYI: this is equivalent to proving that $f(x) \in o(g(x))$, i.e. $f(x)$ is in little o of $g(x)$. $\endgroup$– SchismCommented Feb 21, 2016 at 7:42
-
1$\begingroup$ Not always, see comment by Mark Glisse below. $\endgroup$– SarvottamanandaCommented Feb 21, 2016 at 9:01
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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.
answered Feb 21, 2016 at 6:30
-
1$\begingroup$ I don't like the way you present $o()$ at all. Something like $g(n)=1$, $f(n)=sin(\pi n/2)$ would also answer the question without having $f=o(g)$. $\endgroup$ Commented Feb 21, 2016 at 8:49
-
2$\begingroup$ Your answer is missing a ) on the line just above the graph. $\endgroup$– user12859Commented Feb 21, 2016 at 12:43
$\begingroup$
$\endgroup$
It is easy to find functions with tight upper and lower bounds which have no simultaneous bounds, like:
$\begin{align} f(n) = \begin{cases} n & \text{if } n \text{ is even} \\ n^2 & \text{if } n \text{ is odd} \end{cases} \end{align}$
It is easy to see that $f(n) = O(n^2)$ and $f(n) = \Omega(n)$, none of which can be improved; and that there is no $\alpha$ such that $f(n) = \Theta(n^\alpha)$.
