, если f (n) = o (g (n)), то g (n) + f (n) = Θ (g (n))?

Question

Если мне удалось доказать, что f(n) = o(g(n)) (small o), кажется достаточно разумным, что сумма двух функций f(n) + g(n) должна быть тесно связана с «большой» функцией g(n).

Однако, у меня есть небольшая проблема, доказывающая это.

Answer 1

Следующая рассуждение показывает 'плотно связаны' в смысле асимптотической идентичности (Theta):

f = o(g) 
<=> lim_n->oo (f(n)/g(n)) = 0 
=> lim_n->oo ((f(n)+g(n))/g(n)) 
    = lim_n->oo (f(n)/g(n)) + lim_n->oo (g(n)/g(n)) 
    =   0    +   1 

Answer 2

f(n) = o(g(n)) means that |f(n)|<|C*g(n)| 
+ 
g(n) = Θ(g(n)) means that |C1*g(n)|<=|g(n)|<=|C2*g(n)| 
------------------------------------------------------- 
f(n)+g(n) = Θ(g(n))+o(g(n))=Θ(g(n)) because |C1*g(n)|<=|g(n)+f(n)|<|(C+C2)*g(n)| 

Answer 3

Это довольно легко.

Если f(n) = o(g(n)), то строго мы k, что делает |f(n)| < 0.5 * |g(n)| когда n > k (в соответствии с определением мало-O).

Таким образом, 0.5 * |g(n)| < |f(n) + g(n)| < 1.5 * |g(n)| = Θ(g(n)) для n > k.

QED.

Если f(n) и g(n) все положительно определены, то вам не нужно сильное условие малой о. Однако, когда это не так, тогда требуется сильное условие, потому что иначе f(n) может полностью отменить g(n). (например, f(n) = -g(n))