Search code examples
algorithmbig-oanalysisasymptote

Why does f(n) and g(n) needs to be non-negative function while defining Θ

While reading about Θ definition in CLRS. I found 

The definition of Θ(g(n)) requires that every member f(n) ∈ Θ(g(n))  be
asymptotically nonnegative, that is, that f(n) be nonnegative whenever n is 
sufficiently large. Consequently, the function g(n) itself must be 
asymptotically nonnegative, or else the set Θ(g(n))  **is empty.**

Having one positive function and other being the negative, can possibly not let us do asymptotic analysis.(Θ(g(n)) can be a empty set here).

But

In case where both functions are negative shouldn't be a problem and will count to a valid analysis. Why does author put such restriction on the Θ. Is this useless?

Solution

  • Allowing negative functions is complicating the equivalent definitions, and in fact making them non equivalent:

    1. f(n) is in O(g(n)) if there are constants N,C such that for all n > N: f(n) <= C*g(n)
    2. f(n) is in O(g(n)) if limsup f(n)/g(n) < infinity when n->infinity

    And let's look at two asymptotically negative functions.

    f(n) = -(n^2)
g(n) = -n

    According to definition 1:

    for all n > 2, and with constant 1:
-(n^2) <= 1*-n 
And thus -(n^2) is in O(-n)

    According to definition 2:

    limsup -(n^2) / -n = n = infinity    when  n -> infinity
So, -(n^2) is not in O(-n)

    bottom line: This definition removes this complication, while not losing any usefulness for the big O notation usefulness to analyze algorithms, which is the main focus of the book.

    (To be clear, this probably could have been solved with clever definitions workarounds, but this just complicates things unnecessarily, which the author probably wanted to avoid).