7
$\begingroup$

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.

$\endgroup$

migrated from cstheory.stackexchange.com Sep 30 '12 at 16:32

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ Is your problem covered by the answers to this question? $\endgroup$ – Raphael Sep 30 '12 at 16:59
  • 1
    $\begingroup$ I don't think the answer to this problem applies, but correct me if I'm wrong. The problem you posted is talking about little o and strict definitions, but I'm just interested in knowing why $\Theta$ requires nonnegative members $\endgroup$ – Ockham Sep 30 '12 at 17:29
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What exactly do you mean by the "more complicated definition"? Because it uses $n_0$? $\endgroup$ – phant0m Sep 30 '12 at 21:15
  • $\begingroup$ Note that the definition of CLRS as cited by the OP does not talk about the ratio of $f$ and $g$, and it is in fact not equivalent (without some lifting). $\endgroup$ – Raphael Sep 30 '12 at 21:47
  • $\begingroup$ @Raphael It is somewhat explained what cases the simplified definition does not cover in the last paragraph, but not exactly why. No, it may not talk about the ratio, but it's quite easy to see that this part alone is equivalent. $\endgroup$ – phant0m Sep 30 '12 at 21:50
  • $\begingroup$ @Raphael, I disagree. Both definitions are equivalent under the assumption that $f$ and $g$ are positive (exercise). $\endgroup$ – Yuval Filmus Oct 1 '12 at 3:59
  • $\begingroup$ @YuvalFilmus If we are talking about the same definitions, $f(x) = 1$ and $g(x) = \sin(x)$ is a counter-example. Any pair of functions for which the $\lim f/g$ does not exist breaks it. One has to use $\limsup$ resp. $\liminf$. $\endgroup$ – Raphael Oct 1 '12 at 9:01
2
$\begingroup$

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

$\endgroup$

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.