- #1

Iyan Makusa

- 6

- 2

- Homework Statement
- Prove the following statement:

- Relevant Equations
- ##O(f(n)) + O(g(n)) = O(max(f(n), g(n)))##

So I know the formal definition of Big-O, which states that ##f(n) = O(g(n))## if and only if there exists ##{C > 0, n_0 > 0}## such that ##|f(n)|\leq{C}{g(n)}~\forall{n>n_0}##.

Here's what I think the proof should go (please bear with me, I have no idea what I'm doing):

Suppose there exists a ##{C_1}## and ##C_2## such that ##|h(n)| \leq C_1f(n), |i(n)| \leq C_2g(n)##:

\begin{align}

|h(n)| + |i(n)| \leq C_1f(n) + C_2g(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))

\end{align}

Suppose that ##f(n) > g(n)## and that there exists ##C_3## such that ##|j(n)| \leq C_3f(n)##:

\begin{align}

|h(n)| + |i(n)| \leq C_1f(n) + C_2g(n) &= |j(n)| \leq C_3f(n) \\

C_1f(n) + C_2g(n) &\leq C_3f(n) \\

C_2g(n) &\leq C_3f(n) - C_1f(n) \\

C_2g(n) &\leq f(n)(C_3 - C_1) \\

\frac{g(n)}{f(n)} &\leq \frac{C_3 - C_1}{C_2}

\end{align}

Since ##f(n) > g(n)##:

\begin{align}

\frac{g(n)}{f(n)} < 1 &\leq \frac{C_3 - C_1}{C_2} \\

C_2 &\leq C_3 - C_1

\end{align}

Now that we have values for ##C_1, C_2## and ##C_3##, then ##O(f(n)) + O(g(n)) = O(max(f(n), g(n)))## should hold. ##\blacksquare##

I didn't feel like I did the proof correctly, or at all. Or if I did, there's probably a better way to do this.

Here's what I think the proof should go (please bear with me, I have no idea what I'm doing):

Suppose there exists a ##{C_1}## and ##C_2## such that ##|h(n)| \leq C_1f(n), |i(n)| \leq C_2g(n)##:

\begin{align}

|h(n)| + |i(n)| \leq C_1f(n) + C_2g(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))

\end{align}

Suppose that ##f(n) > g(n)## and that there exists ##C_3## such that ##|j(n)| \leq C_3f(n)##:

\begin{align}

|h(n)| + |i(n)| \leq C_1f(n) + C_2g(n) &= |j(n)| \leq C_3f(n) \\

C_1f(n) + C_2g(n) &\leq C_3f(n) \\

C_2g(n) &\leq C_3f(n) - C_1f(n) \\

C_2g(n) &\leq f(n)(C_3 - C_1) \\

\frac{g(n)}{f(n)} &\leq \frac{C_3 - C_1}{C_2}

\end{align}

Since ##f(n) > g(n)##:

\begin{align}

\frac{g(n)}{f(n)} < 1 &\leq \frac{C_3 - C_1}{C_2} \\

C_2 &\leq C_3 - C_1

\end{align}

Now that we have values for ##C_1, C_2## and ##C_3##, then ##O(f(n)) + O(g(n)) = O(max(f(n), g(n)))## should hold. ##\blacksquare##

I didn't feel like I did the proof correctly, or at all. Or if I did, there's probably a better way to do this.

Last edited: