Is it true that $O(k(n) + m(n))$ is equal to $O(\max\{k(n), m(n)\})$? In one of papers on computational complexity I've found the following statement:
$$O(\log(n) + n(\log S + \log V )) = O(n(\log S + \log V )).$$
Does it follow from the equality given above?
The only similar proof I know is: For $f_1(n) ∈ O(g_1(n))$ and $f_2 ∈ O(g_2(n))$, $f_1(n) + f_2(n) ∈ O(\max\{g_1(n), g_2(n)\})$. I'm almost sure they are related, but for some reason it's not completely clear to me. Thanks for help.
On
Yes.
It's not hard to prove. Let $f(n)\in \mathcal{O}(F(n)), g(n)\in \mathcal{O}(G(n))$, and say the bounding is explicitly
$$|f(n)|\le C_f F(n),\quad |g(n)|\le C_g G(n)$$
for constants, $C_f,C_g>0$. Then
$$|f(n)+g(n)|\le |f(n)|+|g(n)$$ $$\le C_fF(n)+C_gG(n)$$
setting $M=\max\{C_f,C_g\}$ we see this is
$$\le M(F(n)+G(n))$$
$$=M\bigg(\max\{F(n),G(n)\}+\min\{F(n),G(n)\}\bigg)$$
$$\le M\bigg(\max\{F(n),G(n)\}+\max\{F(n),G(n)\}\bigg)$$
$$=2M\max\{F(n),G(n)\}$$
so by definition $(f+g)(n)\in \mathcal{O}\left(\max\{F(n), G(n)\}\right)$.
To see your property, take $g_1 = f_1$ and $g_2 = f_2$ in your known theorem. Then your conjecture holds. Or you can see it as follows. Clearly $O(\max(f_1,f_2))$ is no greater than $O(f_1 + f_2)$, and $O(f_1 + f_2)$ is no greater than $O(2 \max(f_1,f_2))$.