Why does every member $f(n) \in \Theta(g(n))$, and $g(n)$ have to be asymptotically non-negative?

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.

-

1 Answer

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

-
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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 20, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9333606362342834, "perplexity_flag": "middle"}