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