Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

The following is an excerpt from CLRS:

$\Theta(g(n))= \{ f(n) \mid \text{ $\exists c_1,c_2,n_0>0$ such that $0 \le c_1 g(n) \le f(n) \le c_2g(n)$ for all $n \ge n_0$}\}$.

Assuming $n \in \mathbb{N}$, I was unable to find $f(n)$ and $g(n)$ such that the bound does not apply for all $n$.

Note: This question was asked with the flawed assumption that $f(n)$ and $g(n)$ necessarily have natural domains.

share|improve this question
add comment

2 Answers

up vote 0 down vote accepted

You need to have a non-negative sufficiently large input size $n$ from which point on the bound holds. Have a look the Figure 3.1 in CLRS, which shows graphically examples of the $O, \Theta$ and $\Omega$ notation. You can also see why this makes sense. For example, we are interested in knowing how an algorithm's runtime behaves as the input gets larger and larger. Thus, we don't really care too much about small values of $n$.

It is not always the case that for every nonnegative $n$ a bound would hold. For example, consider two functions $f(n)=n$ and $g(n)=n \log n$. We can plot them for a few small values of $n$. $g(n)$ does not dominate $f(n)$ for all values of $n$. For sufficiently large values of $n$, it will. In other words, $f(n) = O(g(n))$. Note that this is only an upper bound, but the idea will be the same for $\Theta$.

share|improve this answer
    
Could you provide an example of two functions where the bound doesn't apply for all $n$? –  Farhad Yusufali Dec 10 '12 at 0:36
    
Yes, thank you. –  Farhad Yusufali Dec 10 '12 at 0:47
    
In your example, it is not true that $g(n) \in O(f(n))$. So $f(n)$ is not in $\Theta(g(n))$. –  usul Dec 10 '12 at 8:08
    
@usul Of course, but it is not supposed to say that. It says that from a certain point on, g is an upper bound for f. The point of the example is to show that while this is true, it does not hold for all n. I believe this is the main point of the question, and the OP agreed it was helpful. Thus I think it's unfair to say my answer is "not useful". –  Juho Dec 10 '12 at 17:51
    
@Juho: I appreciate your helpfulness, but your answer is still incomplete. We aren't concerned with when $g(n)$ dominates $f(n)$, but only with when there exists a $c$ for which $cg(n)$ dominates $f(n)$. In your example, the only reason there is no such $c$ is that $g(1) = 0$ and $f(1) = 1$, so there is no $c$ that makes $c g(1) > f(1)$. But for example the fact that $g(2) < f(2)$ doesn't matter; we can find a constant $c$ such that $cg(2) > f(2)$. –  usul Dec 10 '12 at 20:29
add comment

If we restrict consideration to $\mathbb{N}$ and both functions are strictly positive on every $n \in \mathbb{N}$, then it is true that, if $f(n) \in \Theta(g(n))$, then there exists a $c$ such that $f(n) \leq cg(n)$ for all $n$, and vice versa.

(As pointed out in the comments, if the functions can be negative, then the answer is clearly "no", since we could take $f(1) = -1$ and $g(1) = 1$.)

The proof is straightforward. If $f(n) \in O(g(n))$, then there is an $N$ and a $C$ so that, whenever $n \geq N$, $f(n) \leq C g(n)$.

Now consider $n = 0,1,2,\dots,N-1$. For each $n$, if $g(n) > f(n)$, pick some $c_n$ so that $f(n) \leq c_n g(n)$. We can easily do this because there's only $N$ of these numbers to check.

Now pick $K = \max\{C,c_0,c_1,\dots,c_{N-1}\}$. By construction, $f(n) \leq K g(n)$ for all $n$. So we're done.

The intuition here is not tricky: We know that, if we go far enough out, $C g(x)$ bounds $f(x)$. So we just check all the cases up to that point and pick the biggest bound.

If we consider strictly positive functions defined on the reals, it is not much different to prove that, if $f$ and $g$ are both continuous and bounded below by some $\delta > 0$, we get the same result.

share|improve this answer
    
There is an error in your proof: you cannot always find a $c_n$. A hypothesis that makes the proof work is that $f$ and $g$ are both positive. If e.g. $f(0) = 0$, $g(0) = 1$, $f(1) = 1$, $g(1) = 0$, then the smallest $n_0$ that works in both directions is $2$ or more. For functions defined over reals, there is a constant valid for $[A,\infty)$ if the functions are positive over $[A,\infty)$ (including at $A$). –  Gilles Dec 10 '12 at 14:06
    
@Giles excellent point! I will edit the post. In fact I think we require that f and g are both strictly positive. –  usul Dec 10 '12 at 15:07
add comment

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.