[Solved]: Definition of $\Theta$ for negative functions

Problem Detail: 

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.

Asked By : Ockham

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/4818