Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

The following is an excerpt from CLRS:

The definition of $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.

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

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()$?

share|improve this answer
    
Sorry, I don't. Could you please explain why $\Theta()$ shouldn't be phrased in terms of absolute value? –  Farhad Yusufali Dec 11 '12 at 22:56
1  
@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. –  Steven Stadnicki Dec 11 '12 at 23:02
    
Thank you for the help. –  Farhad Yusufali Dec 11 '12 at 23:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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