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 $nlog 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-30log 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
