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.


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

  • $\begingroup$ Could you provide an example of two functions where the bound doesn't apply for all $n$? $\endgroup$
    – Farhad
    Dec 10 '12 at 0:36
  • $\begingroup$ In your example, it is not true that $g(n) \in O(f(n))$. So $f(n)$ is not in $\Theta(g(n))$. $\endgroup$
    – usul
    Dec 10 '12 at 8:08
  • $\begingroup$ @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". $\endgroup$
    – Juho
    Dec 10 '12 at 17:51
  • $\begingroup$ @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)$. $\endgroup$
    – usul
    Dec 10 '12 at 20:29

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.

  • $\begingroup$ 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$). $\endgroup$ Dec 10 '12 at 14:06
  • $\begingroup$ @Giles excellent point! I will edit the post. In fact I think we require that f and g are both strictly positive. $\endgroup$
    – usul
    Dec 10 '12 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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