0

So I have $4$ functions: $f_1$, $f_2$, $g_1$, $g_2$. I also have in my assumptions that $g_1=\Omega(f_1)$ and $g_2=\Omega(f_2)$. Now I need to prove that $\max(g_1, g_2)=\Omega(f_1+f_2)$. How can this be achieved?

Note that my definition of $\Omega$ is as such: There exists a $C$, and $n_0$ in positive real numbers, such that for all $n$ natural numbers, if $n \ge n_0$, then $C f_1(n) \le g_1(n)$.

The $C$'s are different for the two statements I assume but I need one $C$ that works for their sum in the conclusion. In other words it should be $C(f_1 + f_2) \le \max(g_1,g_2)$

Momo
  • 16,027
dimly_lit_code
  • 7
  • you need some omega in the $f_1+f_2\le\max{g_1,g_2}$, otherwise it's not true – Momo Dec 04 '16 at 00:14
  • Your statement is not true actually. Please follow the latex law and make sure what the question is. – kayak Dec 04 '16 at 00:14
  • basically I have that g1 is omega of f1. g2 is omega of f2. now I need to prove that max(g1, g2) is omega of (f1 + f2) – dimly_lit_code Dec 04 '16 at 00:28

1 Answers1

0

$C_1 f_1(n)\le g_1(n)$ for $n\ge n_1$

$C_2 f_2(n)\le g_2(n)$ for $n\ge n_2$

so if $n_0=\max\{n_1,n_2\}$ and $C_3=\min\{C_1,C_2\}$ we have for $n\ge n_0$:

$C_3 f_1(n)\le g_1(n)$ and $C_3 f_2(n)\le g_2(n)$ so

$C_3 f_1(n)\le \max\{g_1(n),g_2(n)\}$ and $C_3 f_2(n)\le \max\{g_1(n),g_2(n)\}$

So by addition:

$C_3 (f_1(n)+f_2(n))\le 2\max\{g_1(n),g_2(n)\}$

$\frac{C_3}{2} (f_1(n)+f_2(n))\le \max\{g_1(n),g_2(n)\}$

So by taking $C=\frac{C_3}{2}$ we have for $n\ge n_0$

$C (f_1(n)+f_2(n))\le \max\{g_1(n),g_2(n)\}$

so $\max\{g_1,g_2\}=\Omega(f_1+f_2)$

Momo
  • 16,027