Definition of $\Theta$ for negative functions

Question

I'm working out of the 3rd edition CLRS Algorithms textbook and in Chapter 3 a discussion begins about asymptotic notation which starts with $\Theta$ notation. I understood the beginning definition of:

$$\Theta(g(n)) = \{ f(n)\,|\, \exists\, c_1, c_2 > 0, n_0 \in \mathbb{N}: 0 \leq c_1 g(n) \leq f(n) \leq c_2 g(n)\ \ \forall n \geq n_0\}$$

But then on the next page the text says that:

The definition of $\Theta(g(n))$ requires that every member $f(n) \in \Theta(g(n))$ be asymptotically nonnegative, that is, that $f(n)$ be nonnegative whenever $n$ is sufficiently large. (An asymptotically positive function is one that is positive for all sufficiently large $n$.) Consequently, the function g(n) itself must be asymptotically nonnegative, or else the set $\Theta(g(n))$ is empty.

That last part about the how if the function is negative the set $\Theta(g(n))$ is empty and the general requirement of a positive function is sort of confusing. Can anyone out there clarify this definition for me and what it means, possible with an example, it would be much appreciated.

Answer 1

This is just a technicality. In asymptotic analysis we are only "really" interested in positive functions like $n^3$ or $n\log n$. However, if we want to be very formal and general, we could take into account non-positive functions (and that could turn it to be useful, see below). The definition of $\Theta$ states that $f(n) = \Theta(g(n))$ if from some point on, $f(n)/g(n)$ is bounded from both sides by constants, and furthermore $g(n) \geq 0$. (That's what you get if you unroll the definition.) In particular, if $f(n) = \Theta(g(n))$, then from some point on, $g$ is non-negative.

Here is an alternative definition of big $\Theta$. Suppose $f,g \colon \mathbb{N} \rightarrow \mathbb{N}$ are positive functions, that is $f(n),g(n)>0$. Then $f(n) = \Theta(g(n))$ if there exist positive constants $c_1,c_2$ such that $c_1 \leq f(n)/g(n) \leq c_2$. I don't know why the more complicated definition is presented in introductory texts.

What are the advantages of the more complicated definition? It can handle functions which have some non-positive values (there has to be a finite number of them). For example, this definition accommodates the (true) statement $n-10 = \Theta(2n-30\log n)$. Although functions encountered in practice are usually positive, sometimes negative functions could be encountered: for example, say we're interested in some genuine complicated function $k$, and we estimate it from below by a function $t$, which is however negative for small $n$.

Answer 2

Why $\Theta(g)$ may be empty

It follows directly from the definition.

$$\Theta(g(n)) = \{ f(n)\,|\, \exists\, c_1, c_2 > 0, n_0 \in \mathbb{N}: 0 \leq c_1 g(n) \leq f(n) \leq c_2 g(n)\ \ \forall n \geq n_0\}$$

The important part here is this: $ f(n) | \exists\, c_1 > 0: 0 \leq c_1 g(n)$

Obviously, the constraint on $ f$ (as of now, it does not even depend on $f$), states that $g$ multiplied with some positive constant $c_1$ must itself be positive (for large values of $n$, implied from here on).

Of course, if $g$ is not strictly positive, this constraint will prevent all possible functions $f$ from being a member of the set $\Theta(g)$.

It follows that such a set will be empty.

For all $f \in \Theta(g)$, $f$ is strictly positive

This also follows directly from the same part of the definition: $ f(n) | \dots : 0 \leq f(n) $

Obviously, if $f$ is not strictly positive, the condition is not met, hence no such $f$ can be contained in $\Theta(g)$.

Note: I'm not entirely sure what is unclear to you, because all you wrote is "confusing".