1
$\begingroup$

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

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))$.

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .