2
$\begingroup$

The following is an excerpt from CLRS:

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 $g(n)$ is empty.

Intuition suggests that having one function with a positive domain while the other with a negative one perverts the purpose of asymptotic analysis (a measure of the order of growth) as the positive function can be an upper asymptotic bound of the negative function simply on merit of it being positive, even in cases where the negative function grows faster.

In cases where both functions have negative domains, asymptotic analysis would still be a valid measure of the order of growth, making the restriction of both functions having to be positive appear useless.

$\endgroup$

1 Answer 1

4
$\begingroup$

Mostly for convenience's sake. Since big-theta notation specifically tends to be used mostly for algorithmics (as opposed to $O()$ and especially $o()$, which make occasional appearances in more 'traditional' mathematics for talking about goodness of estimates) and is generally used to measure 'usage' quantities of some sort (e.g. CPU cycles, memory, comparisons, etc) there's generally little lost by requiring the quantities involved to be non-negative, and it simplifies some of the definitions and results.

Note that unlike with $\Theta()$, the definitions of $O()$ and $o()$ are often phrased in terms of absolute value, making this point moot - can you see why that idea doesn't make sense for $\Theta()$?

$\endgroup$
2
  • $\begingroup$ Sorry, I don't. Could you please explain why $\Theta()$ shouldn't be phrased in terms of absolute value? $\endgroup$
    – Farhad
    Commented Dec 11, 2012 at 22:56
  • 1
    $\begingroup$ @farhadYusufali Consider the function $f(n) = (-1)^nn^2$. Then $f(n)\in O(n^2)$ and $f(n)\in o(n^3)$ both 'make sense' at some level, but $f(n)\in\Theta(n^2)$ doesn't match with what we intuitively 'want' $\Theta()$ to represent. $\endgroup$ Commented Dec 11, 2012 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.