4
$\begingroup$

I will admit this is a homework problem, but I'm seriously stuck. I'm not looking for answers, but just any hints as to what to do next. Any tips would be appreciated.

I am given:
$$f_1(x) = O(g_1(x)): \exists c_1>0 \; \exists x_1 \; \forall x > x_1 \quad \lvert f_1(x)\rvert \le c_1 \cdot \lvert g_1(x)\rvert$$ $$f_2(x) = O(g_2(x)): \exists c_2>0 \; \exists x_2 \; \forall x > x_2 \quad \lvert f_2(x)\rvert \le c_2 \cdot \lvert g_2(x)\rvert$$

And I have to do the following:

Assume $g_1$ and $g_2$ are non-negative. Find explicit formulas for $c_3$ and $x_3$ (in terms of $c_1, c_2, x_1,$ and $x_2$) so that $$\text{for all } x > x_3, \lvert f_1(x) + f_2(x) \rvert \le c_3 \cdot \lvert g_1(x) + g_2(x) \rvert$$

Essentially I am showing that $f_1(x) + f_2(x) = O(g_1(x) + g_2(x))$.

From the given information I can get that $$ {\lvert f_1(x) \rvert \over \lvert g_1(x)\rvert} \le c_1 \quad \text{and} \quad {\lvert f_2(x) \rvert \over \lvert g_2(x)\rvert} \le c_2$$

But this is where I get stuck. I have no idea how to proceed next. Can anyone give some pointers?

$\endgroup$
2
$\begingroup$

With the given information, if we set $x > \max\{x_1,x_2 \}$, then we get

\begin{align} |f_1(x) + f_2(x)| &\leq |f_1(x)| + |f_2(x)| \\ &\leq c_1|g_1(x)| + c_2 | g_2(x)|\\ &\leq \max \{c_1,c_2 \}(g_1(x) + g_2(x)). \quad(\text{since $g_1,g_2$ are nonnegative} ) \end{align}

So $c_3 = \max \{c_1,c_2 \}$ and $x_3 = \max\{x_1,x_2 \}$ as required.

You can actually go further with this (and it is just one more line) and show that $f_1 + f_2 \in O(\max \{g_1, g_2 \} )$, but I will leave that to you.

I should also note that your question asks for "an explicit formula". The formula for the maximum of two numbers is $$\max \{a,b \} = \frac{a + b + |a - b|}{2}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.