Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
1  
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)$. – Schism Feb 21 at 7:42
1  
Not always, see comment by Mark Glisse below. – Shreesh Feb 21 at 9:01
up vote 7 down vote accepted

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.

enter image description here

share|cite|improve this answer
1  
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)$. – Marc Glisse Feb 21 at 8:49
2  
Your answer is missing a ) on the line just above the graph. ​ ​ – Ricky Demer Feb 21 at 12:43

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)$.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.