Comp Sci Proofing Big-O Notation: O(max(f(n), g(n)))

[Iyan Makusa]

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.

 

[tnich]

I think you are close. I would suggest that the first thing you should do is write out a mathematical statement of what you want to prove. You have written 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}$.

Can you make a similar statement for $h(n)+i(n)=O(max(f(n), g(n)))$, where $h(n)=O(f(n))$ and $i(n)=O(g(n))$?

The way to make a clear proof of something like this is to create a string of $\le$ inequalities with $|h(n) + i(n)|$ at one end and $C_3max\{f(n),g(n)\}$ at the other that hold for all $n>n_3$. Each expression in the string is an upper bound on the previous one. You can figure out $n_3$ and $C_3$ as you go along.

I think you start to go off the track here:

$$C_1f(n) + C_2g(n) = |j(n)|$$

Since $f(n)\le max\{f(n),g(n)\}$ and $g(n)\le max\{f(n),g(n)\}$, you can make an inequality with $C_1f(n) + C_2g(n)$ on one side and $max\{f(n),g(n)\}$ on the other.

Don't forget the "if and only if" in your definition. You are working on the "if" part of the proof. You also need to show the the converse to complete the proof. Although it seems to me that the converse may not be true given your definition of $f(n) = O(g(n))$.

 

[Iyan Makusa]

Can you make a similar statement for $h(n)+i(n)=O(max(f(n), g(n)))$, where $h(n)=O(f(n))$ and $i(n)=O(g(n))$?

$h(n) + i(n) = O(max(f(n),g(n)))$ if and only if there exists $C_3 > 0, n_3 > 0$ such that $|h(n) + i(n)| \leq C_3max(f(n), g(n))~\forall{n>n_3}$

The way to make a clear proof of something like this is to create a string of $\le$ inequalities with $|h(n) + i(n)|$ at one end and $C_3max\{f(n),g(n)\}$ at the other that hold for all $n>n_3$. Each expression in the string is an upper bound on the previous one. You can figure out $n_3$ and $C_3$ as you go along.

I think I can start with that.
\begin{align}
|h(n) + i(n)| &\leq C_3max(f(n),g(n))\\
|h(n) + i(n)| &\leq C_1f(n) + C_2g(n)\\
&\leq max(C_1, C_2)(f(n) + g(n))\\
&\leq C_4max(C_1, C_2)max(f(n), g(n))
\end{align}
where $C_4max(C_1, C_2) = C_3, n > n_3$. I forgot early on the proof that $n_3$ would be $max(n_1, n_2)$ where $h(n), n > n_1; i(n), n > n_2$. So whichever function is the "farther" one would be compared to by $n$.

Since we have found values for $C_3, n_3$ then the proof holds? $\blacksquare{?}$

I'm still not sure about this. I got more help from a slide I found.

 

[tnich]

$h(n) + i(n) = O(max(f(n),g(n)))$ if and only if there exists $C_3 > 0, n_3 > 0$ such that $|h(n) + i(n)| \leq C_3max(f(n), g(n))~\forall{n>n_3}$
I think I can start with that.
\begin{align}
|h(n) + i(n)| &\leq C_3max(f(n),g(n))\\
|h(n) + i(n)| &\leq C_1f(n) + C_2g(n)\\
&\leq max(C_1, C_2)(f(n) + g(n))\\
&\leq C_4max(C_1, C_2)max(f(n), g(n))
\end{align}
where $C_4max(C_1, C_2) = C_3, n > n_3$. I forgot early on the proof that $n_3$ would be $max(n_1, n_2)$ where $h(n), n > n_1; i(n), n > n_2$. So whichever function is the "farther" one would be compared to by $n$.

Since we have found values for $C_3, n_3$ then the proof holds? $\blacksquare{?}$

I'm still not sure about this. I got more help from a slide I found.

That is good, except that you need to show that $C_4$ exists. That is pretty easy, though. If $f(n) \le max\{f(n),g(n)\}$ and $g(n) \le max\{f(n),g(n)\}$, then for what value of $C_4$ is $f(n)+g(n) \le C_4max\{f(n),g(n)\}$?

Also, you ought to include the step $|h(n)+i(n)| \le |h(n)|+|i(n)|$.

 

[Iyan Makusa]

That is good, except that you need to show that $C_4$ exists. That is pretty easy, though. If $f(n) \le max\{f(n),g(n)\}$ and $g(n) \le max\{f(n),g(n)\}$, then for what value of $C_4$ is $f(n)+g(n) \le C_4max\{f(n),g(n)\}$?

Since $f(n) \le max\{f(n),g(n)\}$ and $g(n) \le max\{f(n),g(n)\}$, then:
\begin{align}
f(n) + g(n) &\leq max{f(n), g(n)} + max{f(n),g(n)} \\
&= 2max\{f(n),g(n)\} \leq2max\{f(n),g(n)\}\leq C_4max\{f(n),g(n)\}\\
2 &\leq C_4
\end{align}

But I'm still confused. The entire chain of inequalities (lines 10-12) doesn't contain $f(n) + g(n)$, how does this fit in the proof?