2.19

Definition. [math]f(n)=\Omega(g(n))[/math]  ⇔  ∃ constants [math]c>0,\;n_{0}[/math] such that     [math]\forall n\ge n_{0}: \;f(n)\ge c\;g(n).[/math]

Given.
1. [math]f_{1}(n)=\Omega(g_{1}(n)) \;\Longrightarrow\; \exists\,c_{1}>0,\,n_{1}\;:\;f_{1}(n)\ge c_{1}g_{1}(n)\quad\forall n\ge n_{1}.[/math]
2. [math]f_{2}(n)=\Omega(g_{2}(n)) \;\Longrightarrow\; \exists\,c_{2}>0,\,n_{2}\;:\;f_{2}(n)\ge c_{2}g_{2}(n)\quad\forall n\ge n_{2}.[/math]

Combine the two bounds.
Let [math]c=\min(c_{1},c_{2})>0[/math] and [math]n_{0}=\max(n_{1},n_{2})[/math]. Then for every [math]n\ge n_{0}[/math]:

[math]f_{1}(n)+f_{2}(n)\;\ge\;c_{1}g_{1}(n)+c_{2}g_{2}(n)\;\ge\;c\bigl(g_{1}(n)+g_{2}(n)\bigr).[/math]

Conclusion. We have found constants [math]c>0[/math] and [math]n_{0}[/math] such that [math]\forall n\ge n_{0}:\;f_{1}(n)+f_{2}(n)\ge c\bigl(g_{1}(n)+g_{2}(n)\bigr).[/math] Hence [math]\boxed{\,f_{1}(n)+f_{2}(n)=\Omega\!\bigl(g_{1}(n)+g_{2}(n)\bigr)\,}.[/math]

Back to Chapter 2