Почему f (n) и g (n) должны быть неотрицательной функцией при определении Θ

Question

Читая об определении Θ в CLRS. я нашел

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

Наличие одной положительной функции, а другая - отрицательной, может не позволить нам провести асимптотический анализ ((g(n)) здесь может быть пустым).

Но

В случае, если обе функции отрицательны, не должно быть проблем и будет учитываться при достоверном анализе. Почему автор ставит такое ограничение на Θ. Это бесполезно?

Answer 1

Разрешение отрицательных функций усложняет эквивалентные определения и фактически делает их не эквивалентными:

1. f(n) в O(g(n)) если есть константы N,C такое, что для всех n > N: f(n) <= C*g(n)
2. f(n) в O(g(n)) если limsup f(n)/g(n) < infinity когда n->infinity

И давайте посмотрим на две асимптотически отрицательные функции.

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

Согласно определению 1:

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

Согласно определению 2:

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

Практический результат: это определение устраняет эту сложность, не теряя при этом никакой полезности для использования большой нотации O для анализа алгоритмов, что является основным направлением книги.

(Чтобы быть ясным, это, вероятно, можно было бы решить с помощью умных обходных путей с определениями, но это просто излишне усложняет ситуацию, чего автор, вероятно, хотел избежать).