Prove that for all functions $g: N \to R^{\geq 0}$, and all numbers $a$ in $R^{\geq 0}$, if $g \in \Omega(1)$ then $a + g \in \Theta(g)$

23 Views Asked by At

Here is a more readable version of the question:

Prove that for all functions $g: \mathbb{N}\to\mathbb{R}^{\geq 0}$, and all numbers $a \in \mathbb{R}^{\geq 0}$, if $g \in \Omega(1)$ then $a + g \in \Theta(g)$

What I've done so far:

In order for $a + g\in\Theta(g)$, $a+g \in \mathcal{O}(g) \wedge a + g \in \Omega(g)$.

Expanding our assumption, we get:

$\exists c_1, n_1 \in \mathbb{R}^{+}, \forall n \in \mathbb{N}, n \geq n_1 \implies g(n) \geq c_1$

Proving $a + g \in \Omega(g)$:

Expanding the definition, we get:

$\exists c_2,n_2 \in \mathbb{R}^{+}, \forall n \in \mathbb{N}, n \geq n_2 \implies a + g(n) \geq c_2*g(n)$

Let $c_2 = 1$ and $n_2 = n_1$. Let $n \in \mathbb{N}$. Assume $n \geq n_2$. Prove $a + g(n) \geq c_2 * g(n)$.

$g(n) = g(n)\\ \implies g(n) \geq g(n)\\ \Leftrightarrow c_2 * g(n) \geq c_2 * g(n)\\ \Leftrightarrow g(n) \geq g(n) \text{ (since $c_2 = 1$)}\\\Leftrightarrow a+g(n) \geq g(n) \text{ (making left side bigger since $a \in \mathbb{R}^{\geq 0}$)}$

Proving $a+g \in \mathcal{O}(g)$:

Expanding the definition, we get:

$\exists c_3,n_3 \in \mathbb{R}^+, \forall n \in \mathbb{N}, n \geq n_3 \implies a + g(n) \leq c_3 * g(n)$

I'm struggling here since I'm not really sure what value of $c_3$ I should be using or how to derive one. (I've tried using my assumption of $g(n) \geq c_1$ but I don't really know where to go from there). Any help is greatly appreciated and I apologize for any formatting errors in advance. Thank you.